Early growth and body composition may influence the risk of obesity and health in adulthood. Few studies have examined how under nutrition is associated with body composition in early life. We assessed stunting and wasting as correlates of body composition in young Kenyan children. Nested in a randomized controlled nutrition trial, this longitudinal study assessed fat and fat-free mass (FM, FFM) using deuterium dilution technique among children at age 6 and 15 months. This trial was registered at http://controlled-trials.com/ (ISRCTN30012997). Cross-sectional and longitudinal associations between z-score categories of length-for-age (LAZ) or weight-for-length (WLZ) and FM, FFM, fat mass index (FMI), fat-free mass index (FFMI), triceps, and subscapular skinfolds were analyzed by linear mixed models. Among the 499 children enrolled, breastfeeding declined from 99% to 87%, stunting increased from 13% to 32%, and wasting remained at 2% to 3% between 6 and 15 mo. Compared with LAZ >0, stunted children had a 1.12 kg (95% CI: 0.88, 1.36; P < 0.001) lower FFM at 6 mo and increased to 1.59 kg (95% CI: 1.25, 1.94; P < 0.001) at 15 mo, corresponding to differences of 18% and 17%, respectively. When analyzing FFMI, the deficit in FFM tended to be less than proportional to children’s height at 6 mo (P ≤ 0.060) but not at 15 mo (P > 0.40). Stunting was associated with 0.28 kg (95% CI: 0.09, 0.47; P = 0.004) lower FM at 6 mo. However, this association was not significant at 15 mo, and stunting was not associated with FMI at any time point. A lower WLZ was generally associated with lower FM, FFM, FMI, and FFMI at 6 and 15 mo. Differences in FFM, but not FM, increased with time, whereas FFMI differences did not change, and FMI differences generally decreased with time. Overall, low LAZ and WLZ among young Kenyan children were associated with reduced lean tissue, which may have long-term health consequences.