Background/objectives: The role of infant feeding practices in longitudinal growth trajectories in children remains equivocal. This study utilised two longitudinal approaches to examine the associations of infant feeding mode (breastfeeding, mixed feeding, formula feeding), breastfeeding duration, and the timing of solid foods introduction with body mass index (BMI) z-score in early childhood. Subjects/methods: Secondary analyses of data from the Healthy Beginnings Trial were conducted. Infant feeding practices were reported by mothers at 6, 12, and 24 months of child age. Child weight and length were measured at birth, 12, 24, 42, and 60 months. Two longitudinal approaches: linear spline multilevel model (LSMM) and group-based trajectory modelling (GBTM) were used to describe BMI z-score trajectories and assess its associations with infant feeding practices. Results: The LSMM approach demonstrated that the breastfeeding group showed lower BMI z-scores from ages 12 to 60 months than the mixed feeding and formula feeding groups. Children who were breastfed for ≥ 6 versus < 6 months exhibited a lower BMI z-score trajectory from ages 12 to 60 months. Results from the GBTM approach revealed that the mixed feeding (OR: 1.83, 95%CI 1.04, 3.21) and the formula feeding group (OR: 2.00, 95%CI 0.67, 5.92) showed a tendency for higher odds of following the “High BMIz” trajectory than the breastfeeding group. Breastfeeding duration ≥6 versus < 6 months was linked with lower odds of following the “High BMIz” trajectory (OR 0.65, 95%CI 0.43, 0.98). Both approaches revealed no evidence of an association between the timing of solid foods introduction and BMI z-score trajectory. Conclusions: The two longitudinal approaches revealed similar findings that infant feeding mode and breastfeeding duration, but not the timing of solid foods introduction, were associated with BMI z-score trajectory in early childhood. The findings provide robust longitudinal evidence to encourage and support extended breastfeeding for childhood obesity prevention.