The aim of this study was to investigate the effect of physical activity (PA) levels over 36 months on the cardiorespiratory fitness (CRF) of children and adolescents. This was a longitudinal study carried out from 2016 to 2019 with 127 children and adolescents (82 males and 45 females) aged 13.5 ± 1.2 years at baseline. The 20 m shuttle run test (20 mSRT) was used to predict CRF. The questionnaires PAQ-C and PAQ-A were used to investigate PA. The 2 × 4 repeated measures ANCOVA was used, and the significance level was p ≤ 0.05. There was a linear trend in the interaction between level of PA and CRF throughout the 36-month study period in both sexes (males—distance covered: F1.78 = 4.567; p = 0.04; VO2max: F1.78 = 5.323; p = 0.02; females—distance covered: F1.41 = 6.989; p = 0.01; VO2max: F1.41 = 6.585; p = 0.01). Physically active males showed a gradual increase in CRF throughout the analyzed period. For females, CRF remained constant in the first 24 months, showing a slight increase only after 36 months in physically active ones. The findings of this study reinforce the importance of PA throughout childhood and adolescence to improve CRF.