Fecal samples were obtained from a cohort of 330 healthy Danish infants at 9, 18 and 36 months after birth, enabling characterization of interbacterial relationships by use of quantitative PCR targeting 31 selected bacterial 16S rRNA gene targets representing different phylogenetic levels. Nutritional parameters and measures of growth and body composition were determined and investigated in relation to the observed development in microbiota composition. We found that significant changes in the gut microbiota occurred, particularly from age 9 to 18 months, where cessation of breastfeeding and introduction of a complementary feeding induces replacement of microbiota characterized by lactobacilli, bifidobacteria and Enterobacteriaceae with a microbiota dominated by Clostridium spp. and Bacteroides spp. Classification of samples by a proxy 'enterotype' based on the relative levels of Bacteroides spp. and Prevotella spp. showed that 'enterotype' establishment occurs between 9 and 36 months. 30% of the individuals shifted 'enterotype' between 18 and 36 months. The composition of the microbiota was most pronouncedly influenced by the time of cessation of breastfeeding. From 9 to 18 months, a positive correlation was observed between the increase in Body Mass Index and the increase of the Short Chain Fatty Acid producing clostridia, C. leptum group and E. halii. Considering previously established positive associations between rapid infant weight gain, early breastfeeding discontinuation and later life obesity, the corresponding microbial findings seen here warrant attention.