Background: Development of body composition (BC) may be disrupted in children with stunting. Such disruption may affect the later risk of excess adiposity and metabolic health, yet few studies have investigated correlates of BC in children with stunting. Objectives: We aimed to investigate nutritional status, infection and inflammation, breastfeeding behaviors, and other factors as correlates of BC in children with stunting. Methods: Among Ugandan children with a height-for-age z-score <−2, BC was estimated using bioelectrical impedance analysis and compared with United Kingdom references. We used multiple linear regression analysis to identify correlates of fat mass (FM), fat-free mass (FFM), FM-index (FMI), and FFM index (FFMI) and height, adjusting for gender and age. Results: In 750 children aged 1–5 y, FMI was 0.46 (95% confidence interval [CI]: 0.38, 0.54] and FFMI 0.18 [95% CI: 0.11, 0.26) z-scores lower than United Kingdom references. Elevated serum α₁-acid glycoprotein was associated with 1.14 [0.76, 1.52] cm lower height, 0.50 [0.35, 0.65] kg/m² less FFMI, and 0.48 [0.31, 0.66] kg/m² greater FMI. Similar, weaker, associations for elevated serum C-reactive protein were detected. A positive malaria rapid test was associated with 0.64 [0.25, 1.02] cm shorter height, but 0.36 [0.18, 0.54] kg/m² greater FMI. Anemia (according to hemoglobin) was associated with 0.20 [0.07, 0.33] kg less FFM in proportion to shorter height. Longer breastfeeding duration was associated with 0.03 [0.02, 0.04] kg greater FFM per month, in proportion to greater height. Conclusions: These children exhibited deficits in FM and FFM, proportionally to their stunted height, compared with United Kingdom references. Systemic inflammation correlated inversely with linear growth and FFM but positively with fatness, making it a possible target for intervention where fat-free tissue accretion is desirable. Longer breastfeeding may offer protection to lean linear growth, but findings for micronutrients were less clear. Longitudinal studies are warranted to support these findings. The study was registered at www.isrctn.com (Ref. ISRCTN13093195).