Aims: The aims were (1) to analyse the cross-sectional and longitudinal associations between children’s cardiorespiratory fitness (CRF) and health-related quality of life (HRQoL) and (2) to examine whether these associations were mediated by physical activity self-efficacy and physical activity enjoyment. Methods: This study involved 383 children (10.0 ± 0.5 years) recruited from 20 primary schools in northwest England. Data were collected on two occasions 12 weeks apart. The number of laps completed in the 20-m Shuttle Run Test was used as the CRF indicator. HRQoL was assessed using the KIDSCREEN-10 questionnaire. Physical activity self-efficacy and enjoyment were assessed with the social-cognitive and Physical Activity Enjoyment Scale questionnaires, respectively. Linear mixed models with random intercepts (schools) assessed associations between CRF and HRQoL cross-sectionally, and longitudinally. Boot-strapped mediation procedures were performed, and indirect effects (IE) with 95% confidence intervals (CI) not including zero considered as statistically significant. Analyses were adjusted for sex, time of the year, socioeconomic status, waist-to-height ratio, maturation, and physical activity. Results: CRF was cross-sectionally associated with HRQoL (β = 0.09, 95% CI = 0.02, 0.16; p = .015). In the longitudinal analysis, CRF at baseline was associated with HRQoL at 12 weeks after additionally controlling for baseline HRQoL (β = 0.08, 95% CI = 0.002; p = .15, p = .045). Cross-sectionally, physical activity self-efficacy and enjoyment acted individually as mediators in the relationship between CRF and HRQoL (IE = 0.069, 95% CI = 0.038; p = .105 and IE = 0.045, 95% CI = 0.016; p = .080, respectively). In the longitudinal analysis, physical activity self-efficacy showed a significant mediating effect (IE = 0.025, 95% CI = 0.004; p = .054). Conclusion: Our findings highlight the influence of CRF on children’s psychological correlates of physical activity and their overall HRQoL.