Gastrointestinal (GI) microbiota composition differs between breastfed and formula-fed infants. Today’s infant formulas are often fortified with prebiotics to better mimic properties of human milk with respect to its effect on GI microbiota composition and function. We used Illumina HiSeq sequencing of PCR-amplified 16S rRNA gene fragments to investigate the composition of faecal microbiota in 2–12 week old infants receiving either breastmilk, infant formulas fortified with prebiotics, or mixed feeding. We compared these results with results from infants fed traditional formulas used in the Netherlands in 2002–2003, which contained no added prebiotics. We showed that today’s formulas supplemented with either scGOS (0.24–0.50 g/100 ml) or scGOS and lcFOS (at a 9:1 ratio; total 0.6 g/100 ml) had a strong bifidogenic effect as compared to traditional formulas, and they also resulted in altered patterns of microbial colonisation within the developing infant gastrointestinal tract. We identified three microbial states (or developmental stages) in the first 12 weeks of life, with a gradual transition pattern towards a bifidobacteria dominated state. In infants receiving only fortified formulas, this transition towards the bifidobacteria dominated state was accelerated, whereas in infants receiving mixed feeding the transition was delayed, as compared to exclusively breastfed infants.