Early life is critical for the programming of body composition. The literature links perinatal factors with fat mass development and its future effects (e.g., obesity); however, little evidence exists between early life factors and lean body mass (LBM). This study follows up on a cohort of 416 Spanish children at ages six to eight, previously evaluated at birth in the CALINA study. Here, we studied the association between early life factors, LBM, and limb strength. Parental origin/nutritional status, maternal smoking during pregnancy, gestational diabetes/weight gain/age, birth weight (BW), early feeding, and rapid weight gain (RWG) were collected from primary care records. Bioimpedance analysis, dual-energy X-ray absorptiometry, peripheral quantitative computed tomography, and a handgrip/standing long jump test were used to assess fat-free mass index (FFMI), total lean soft tissue mass index (TLSTMI), muscle cross-sectional area index (MCSAI), and limb strength, respectively. In girls, maternal smoking, gestational age, and BW were positively associated with FFM/LSTM. In boys, the parents’ BMI, BW, and RWG were positively associated with FFM/LSTM. BW was associated with handgrip strength in both. Maternal BMI in girls and RWG in boys were negatively associated with the standing long jump. Early life programming plays a key role in determining LBM in children.