Heart rate variability (HRV) measurement provides non-invasive assessment of autonomic stability and cardiometabolic disease risk. Insufficient physical activity in early childhood may contribute to negative cardiometabolic health. The Active Early Learning (AEL) study was a 6-month randomised controlled trial investigating the effects of a physical activity-based program incorporating movement within the daily curriculum of preschool children. The current study assessed the effects of the AEL intervention on HRV as a measure of cardiac vagal control. Children aged between 3–5 years and enrolled in a preschool with an attendance of ≥15 children were eligible. Physical activity was recorded using an Actigraph wGT3x accelerometer worn at the waist of participants over 3 consecutive days. A Polar H10 chest strap measured HRV with the HF-band and RMSSD representing cardiac vagal control. After 6 months of the AEL trial, linear mixed model analyses revealed a significant intervention effect for increased HF (p = 0.044). The control group did not demonstrate changes in cardiac vagal control after the intervention ceased. Independent of age, sex, physical activity and BMI, the AEL study elicited significant improvements in the cardiac vagal control of participants who received the intervention. Findings highlight the importance of investigating HRV for assessing the cardiometabolic health in young children. ANZCTR trial registration number: ACTRN12619000638134. Novelty: • The AEL curriculum improved child HRV independent of age, sex, physical activity and BMI. • Heart rate and RR intervals did not demonstrate changes for the intervention and control groups. • Multivariate programs for developing physical competence, confidence, knowledge and motivation may improve child health.