Physical inactivity is a significant risk factor for childhood obesity. Preventing obesity in the early years reduces the risk of developing chronic health conditions later. Early childhood education and care (ECEC) services are important settings to establish good preschooler physical activity behaviors. This natural experiment investigated the influence of ECEC outdoor physical environment upgrade on preschoolers’ physical activity (aged 2–5 years). Centers implemented upgrades without researcher input. Physical activity was measured by 7-day accelerometry for intervention (n = 159; 6 centers) and control (n = 138; 5 centers) groups. ECEC outdoor space was assessed using a modified Environment and Policy Assessment and Observation (EPAO) Instrument. Key outcomes were measured at baseline and 6–12 months follow-up. Fixed sandboxes, balls, portable slides, portable floor play equipment (e.g., tumbling mats), and natural grassed areas were positively associated with activity levels; fixed tunnels and twirling equipment were negatively associated with activity levels (all p < 0.05). Post-upgrade portable play equipment (balls, twirling equipment, slides, floor play equipment) increased intervention preschoolers’ moderate-vigorous physical activity (MVPA) levels compared to control (p < 0.05). Intervention preschoolers were more active than control at follow-up (58.09 vs. 42.13 min/day increase in total physical activity; 30.46 vs. 19.16 min/day increase in MVPA (all p < 0.001)). Since few preschoolers meet daily activity recommendations while at ECEC, the findings may help ECEC providers to optimize outdoor physical environments and encourage more active play among preschoolers.