Abstract Background Cardiovascular fitness is strongly linked with metabolic risk; however, research is limited in preschool children. Although there is currently no simple validated measure of fitness in preschool children, heart rate recovery has been highlighted as an easily accessible and non-invasive predictor of cardiovascular risk in school-aged children and adolescents. We aimed to investigate whether heart rate recovery was associated with adiposity and blood pressure in 5-year-olds. Study design This is a secondary analysis of 272 5-year-olds from the ROLO (Randomised cOntrol trial of LOw glycaemic index diet in pregnancy to prevent recurrence of macrosomia) Kids study. Three-minute step tests were completed by 272 participants to determine heart rate recovery duration. Body mass index (BMI), circumferences, skinfold thickness, heart rate, and blood pressure were collected. Independent t-tests, Mann-Whitney U, and Chi-square tests were used to compare participants. Linear regression models examined associations between heart rate recovery and child adiposity. Confounders included child sex, age at study visit, breastfeeding, and perceived effort in the step test. Results The median (IQR) age at the study visit was 5.13 (0.16) years. 16.2% (n = 44) had overweight and 4.4% (n = 12) had obesity based on their BMI centile. Boys had a quicker mean (SD) heart rate recovery after the step test than girls (112.5 (47.7) seconds vs. 128.8 (62.5) seconds, p = 0.02). Participants with a slower recovery time (> 105 s) had higher median (IQR) sum of skinfolds (35.5 (11.8) mm vs. 34.0 (10.0) mm, p = 0.02) and median (IQR) sum of subscapular and triceps skinfold (15.6 (4.4) mm vs. 14.4 (4.0) mm, p = 0.02) compared to participants with a quicker recovery time. After adjusting for confounders (child sex, age at study visit, breastfeeding, effort in the step test), linear regression analyses revealed heart rate recovery time after stepping was positively associated with sum of skinfolds (B = 0.034, 95% CI: 0.01, 0.06, p = 0.007). Conclusion Child adiposity was positively associated with heart rate recovery time after the step test. A simple stepping test could be used as a non-invasive and inexpensive fitness tool in 5-year-olds. Additional research is needed to validate the ROLO Kids step test in preschool children.