Objective: This study examined the relative impact of breastfeeding duration and timing of solids introduction on BMI z score (BMIz) trajectory in early childhood. Methods: This study conducted secondary analyses of data from the Melbourne Infant Feeding, Activity and Nutrition Trial (InFANT) Program (N = 542), a prospective cohort study with data collected at birth and 3, 9, 18, 42, and 60 months. Linear spline multilevel models were performed. Results: Differential growth rates were observed from birth to 3 months and from 9 to 18 months by breastfeeding duration (≥ 6 vs. < 6 months) and timing of solids introduction (before vs. after 6 months). Children who were breastfed for ≥ 6 versus < 6 months had lower BMIz at all ages from 3 to 60 months. The difference remained after adjusting for child and maternal factors, and the adjusted mean differences in BMIz at 3, 9, 18, 42, and 60 months were −0.34, −0.44, −0.13, −0.19, and −0.23, respectively. Children who received solids before versus after 6 months of age had higher BMIz at 18 and 42 months, but adjustment for child and maternal factors attenuated these differences. Conclusions: Longer breastfeeding duration was associated with lower BMIz to 5 years of age, providing further support for infant feeding guidelines to prolong breastfeeding duration for healthy growth.