Reduced heart rate variability (HRV) is associated with overweight and obesity in adults. However, little is known about this relationship in early childhood. We investigated the relationship between resting vagally-mediated HRV and body mass index (BMI) in Australian preschool children. Children were recruited from 13 non-government early learning centres located in Queensland and New South Wales, Australia. From this population-based sample, data from 146 healthy children (58 females) between 3 and 5 years of age (mean age 4.35 ± 0.44 years) were analysed. BMI was calculated from child body weight and height. 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 seated, resting RR intervals for the calculation of HRV with the root mean square of successive differences (RMSSD) reflecting vagally-mediated activity. The relationship between HRV and BMI was analysed using a linear mixed model adjusted for age, sex and physical activity. Analysis revealed that RMSSD (ln) demonstrated a significant inverse relationship with BMI (β = -0.06; 95% CI = -0.12 – −0.01; p = 0.032), and the model accounted for 23% of the variance in RMSSD (ln). Notably, a one unit increase in BMI resulted in a reduction in RMSDD (ln) of 0.06. This investigation demonstrated evidence for a significant inverse linear relationship between vagally-mediated HRV and BMI in 3 – 5-year-old Australian children, similar to that of adults. Furthermore, this relationship was independent of age, sex and physical activity levels. Results may indicate that the cardiometabolic health of preschool children is, in part, influenced by the relationship between vagally-mediated HRV and weight status.