Background: To examine the effect of early menarche (EM) on adolescent body composition and fat distribution, and to explore the possible contribution of birth weight (BW) to this relationship. Methods: From the cross-sectional AVENA study, 788 girls (aged 13–18.5 years) were selected. Post-menarcheal body composition was estimated by anthropometric methods. Results: BW Z-score was associated with age at menarche (β = 0.496, p < 0.001). EM (age of menarche <12 years) adolescents were shorter, had a higher body mass index (BMI), fat free mass index (FFMI), fat mass index (FMI) and waist circumference (all p < 0.01). BW was associated with height (p < 0.001), BMI Z-score (p < 0.01), FFMI (p < 0.01) and FMI (p < 0.05). These relationships did not change when the analysis was controlled for age of menarche. Height and FFM were lower in EM (p < 0.01), but these effects seem to be due to the BW (p < 0.01). Conclusion: EM was strongly associated with unhealthy body composition in female adolescents, but these relationships seem to be due to the programming effect of BW.