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, when cessation of breastfeeding and introduction of a complementary feeding induce replacement of a 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. Thirty percent 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, the Clostridum leptum group, and Eubacterium hallii. 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.