Background: Physical activity professional development programs for Early Childhood Education and Care (ECEC) educators are a viable strategy for improving preschool children’s physical activity behavior. This pilot intervention evaluated the effectiveness of ‘nature play’ and ‘fundamental movement skills’ (FMS) professional development programs on ECEC educators’ practices on physical activity. Methods: 148 ECEC educators from 20 ECEC centers took part in either the Nature play or FMS professional development programs in Perth, Western Australia. Educators self-reported their physical activity related practices at baseline and three months post-professional development training, using established items. Wilcoxon’s test and adjusted models using Mann–Whitney U tests were run at the individual educator level to examine the change between baseline and post-professional development educator physical activity behavior. Results: Educators’ self-efficacy to engage children to be active significantly increased in both the Nature play and FMS professional development programs (p < 0.05). In the Nature play professional development program, ECEC educators’ perceived time set aside for children to participate in nature-based play increased by 9.2%, and their perceived behavioral control for supporting general and nature-based play activities for preschool children increased by 5% and 10.3%, respectively (p < 0.05). However, these results were no longer significant after adjusting for educator socio-demographics. Conclusion: Both the Nature play and FMS professional development programs were effective in improving educators’ self-efficacy to engage children to be active in Nature play or FMS activities. Larger pragmatic trials are required to confirm the impact of these professional development programs on educator perceived physical activity behavior.