Objectives: The purpose of this study was to evaluate the linear and curvilinear relationship between body mass index (BMI) and physical fitness in children and adolescents. Methods: Participants were 4567 (2505 girls) children aged 6–16 years. Weight and height were measured and BMI was calculated and adjusted for age and sex using WHO z-scores. Physical fitness was evaluated with the following tests: Yo-Yo test, standing long jump, seated 2-kg medicine ball throw, and 20-m dash. Participants were grouped into two groups according to their maturity status, estimated as years from peak height velocity. Associations were determined with linear and nonlinear quadratic regression models. Results: The nonlinear quadratic regression coefficient was significant for the 20-m dash among girls of both maturity status levels, and in maturity status level 1 boys; for the standing long jump among boys of both maturity status levels, and in maturity status level 1 girls. The Yo-Yo test was only significant for maturity status level 1 boys. For the medicine ball throw, the linear regression coefficient was significant for both maturity status levels in both sexes. Almost all physical fitness items were observed to have meaningfully large nonlinear relationships with BMIz, but they were not all significant due to the small sample size, especially in maturity status level 2. Conclusion: The association between BMI and physical fitness is nonlinear in the majority of its components, and those with lower and higher BMI had poorer fitness.