Background: Little is known about the relationship between body composition and physical fitness in 14 year-old high school adolescents of South Africa. Baseline data from a longitudinal study on physical activity and health (PAHLS) may provide valuable information for future studies, hence to inform public health policy makers. The objectives of this study are to determine the prevalence of underweight, normal weight and overweight among adolescents aged 14 years in the Tlokwe Local Municipality of the North West Province of South Africa, and to assess the association between physical fitness and body composition separately for boys and girls, adjusted for race and locality. Methods: Body weight, height and triceps, and subscapular skinfolds of 256 adolescents (100 boys and 156 girls) aged 14 years were measured, and percentage body fat and body mass index (BMI) were calculated. BMI was used to determine underweight, normal weight and overweight based on the standard criterion. Physical fitness was assessed by standing broad jump, bent arm hang and sit-ups according to the EUROFIT fitness standard procedures. Multinomial logistic regression analyses stratified for gender and adjusted for race (black or white), and the locality (urban or township) of the schools were used to analyze the data. Results: In the total group 35.9% were underweight and 13.7% overweight. Boys were more underweight (44%) than girls (30.7%). The prevalence of overweight was 8% in boys and 17.3% in girls. BMI was strongly (p = 0.01) related with percentage body fat. Strong and significant positive associations between physical fitness and BMI for the underweight girls with high physical fitness scores (OR, 10.69 [95%CI: 2.81-40.73], and overweight girls with high physical fitness scores (OR, 0.11 [95%CI: 0.03-0.50]) were found. Non-significant weaker positive relationship between physical fitness and BMI for the underweight boys with high physical fitness scores (OR, 1.80 [95%CI: 0.63-5.09]), and the overweight boys with high physical fitness scores (OR, 0.18 [95%CI: 0.02-1.78]) were found. Conclusion: Both underweight and overweight among boys and girls in Tlokwe Local Municipality exist, and their effects on physical fitness performances were also noticed. As such, strategic physical activity, interventions or follow-up studies recognizing this relationship particularly in the overweight adolescents are needed. In addition, authorities in health and education departments dealing with adolescents should make use of this evidence base information in policies development. © 2012 Monyeki et al.; licensee BioMed Central Ltd.