Postnatal growth restriction and deficits in fat-free mass are associated with impaired neurodevelopment. The optimal body composition to support normal brain growth and development remains unclear. This study investigated the association between body composition and brain size in preterm infants. We included 118 infants born <28 weeks of gestation between 2017–2021, who underwent body composition (fat-free mass (FFM) and fat mass (FM)) and cerebral magnetic resonance imaging to quantify brain size (cerebral biparietal diameter (cBPD), bone biparietal diameter (bBPD), interhemispheric distance (IHD), transverse cerebellar diameter (tCD)) at term-equivalent age. FFM Z-Score significantly correlated with higher cBPD Z-Score (rs = 0.69; p < 0.001), bBPD Z-Score (rs = 0.48; p < 0.001) and tCD Z-Score (rs = 0.30; p = 0.002); FM Z-Score significantly correlated with lower brain size (cBPD Z-Score (rs = −0.32; p < 0.001) and bBPD Z-Score (rs = −0.42; p < 0.001). In contrast weight (rs = 0.08), length (rs = −0.01) and head circumference Z-Score (rs = 0.14) did not. Linear regression model adjusted for important neonatal variables revealed that FFM Z-Score was independently and significantly associated with higher cBPD Z-Score (median 0.50, 95% CI: 0.59, 0.43; p < 0.001) and bBPD Z-Score (median 0.31, 95% CI: 0.42, 0.19; p < 0.001); FM Z-Score was independently and significantly associated with lower cBPD Z-Score (median −0.27, 95% CI: −0.42, −0.11; p < 0.001) and bBPD Z-Score (median −0.32, 95% CI: −0.45, −0.18; p < 0.001). Higher FFM Z-Score and lower FM Z-scores were significantly associated with larger brain size at term-equivalent age. These results indicate that early body composition might be a useful tool to evaluate and eventually optimize brain growth and neurodevelopment.