There is currently limited evidence on parents’ and early childhood educators’ perspectives on implementing programs that combine cognitive and motor tasks in early childhood. An online survey was distributed across Australia through social network platforms and emails at preschool centres, asking 65 parents of preschool children and early childhood educators about their preferences on program delivery, duration, and mode. Responses from the survey were evaluated in order to develop and pilot a 4 week home-based (n = 5 parents) and a 6 week school-based program (n = 5 educators) including cognitively engaging physical activity, requesting parents’ and educators’ perspectives, respectively, about the program components. Results from the online survey showed a preference for programs with online (e.g., video-based) compared to traditional delivery (e.g., books), emphasising the potential benefits on children’s physical activity levels, sleep, and cognitive function. However, after piloting the program, educators preferred to use the book version instead of the video. This program has the potential to become part of daily regular practice. Barriers reported include logistics issues (i.e., book size), connectivity issues with internet, and the need for varying activities.