Rapid growth during infancy is associated with increased risk of overweight and obesity and differences in weight gain are at least partly explained by means of infant feeding. The aim was to assess the associations between infant feeding practice in early infancy and body mass index (BMI) at 6 years of age. Icelandic infants (n = 154) were prospectively followed from birth to 12 months and again at age 6 years. Birth weight and length were gathered from maternity wards, and healthcare centers provided the measurements made during infancy up to 18 months of age. Information on breastfeeding practices was documented 0-12 months and a 24-h dietary record was collected at 5 months. Changes in infant weight gain were calculated from birth to 18 months. Linear regression analyses were performed to examine associations between infant feeding practice at 5 months and body mass index (BMI) at 6 years. Infants who were formula-fed at 5 months of age grew faster, particularly between 2 and 6 months, compared to exclusively breastfed infants. At age 6 years, BMI was on average 1.1 kg/m2 (95% CI 0.2, 2.0) higher among infants who were formula fed and also receiving solid foods at 5 months of age compared to those exclusively breastfed. In a high-income country such as Iceland, early introduction of solid foods seems to further increase the risk of high childhood BMI among formula fed infants compared with exclusively breastfed infants, although further studies with greater power are needed.