Objective: To assess the association between body mass index (BMI) and physical fitness index (PFI) among children and adolescents in Xinjiang Uyghur Autonomous Region, China. Methods: In total, 17,618 children and adolescents aged 7–18 years from the selected region were enrolled in this cross-sectional study (8,800 boys and 8,818 girls). Participants were stratified by age and sex and divided into five groups by BMI percentiles: very low (BMI <5th percentile); low, (5th ≤ BMI < 15th percentile); normal (15th ≤ BMI < 85th percentile); high (85th ≤ BMI < 95th percentile); and very high (BMI ≥95th percentile). PFI was assessed by height, weight, and five health-related fitness indicators (grip strength, standing long jump, sit and reach, 50 m dash, and endurance run). Results: BMI was significantly associated with PFI during adolescence (13–18 years) in boys and pre-adolescence (7–12 years) in girls. Between the ages of 13 and 18 years, an increase in BMI had a greater impact on PFI in boys than girls. PFI showed a parabolic curvilinear relationship with BMI. Conclusion: Children and adolescents in China’s Xinjiang Uyghur Autonomous Region with a normal BMI demonstrated good physical fitness. A BMI below or above the normal range may contribute to poor physical fitness. The relationship between BMI and PFI shows an inverted U-shaped curve.