Non-digestible milk oligosaccharides were proposed as receptor decoys for pathogens and as nutrients for beneficial gut commensals like bifidobacteria. Bovine milk contains oligosaccharides, some of which are structurally identical or similar to those found in human milk. In a controlled, randomized double-blinded clinical trial we tested the effect of feeding a formula supplemented with a mixture of bovine milk-derived oligosaccharides (BMOS) generated from whey permeate, containing galacto-oligosaccharides and 3'- and 6'-sialyllactose, and the probiotic Bifidobacterium animalis subsp. lactis (B. lactis) strain CNCM I-3446. Breastfed infants served as reference group. Compared with a non-supplemented control formula, the test formula showed a similar tolerability and supported a similar growth in healthy newborns followed for 12 weeks. The control, but not the test group, differed from the breast-fed reference group by a higher faecal pH and a significantly higher diversity of the faecal microbiota. In the test group the probiotic B. lactis increased by 100-fold in the stool and was detected in all supplemented infants. BMOS stimulated a marked shift to a bifidobacterium-dominated faecal microbiota via increases in endogenous bifidobacteria (B. longum, B. breve, B. bifidum, B. pseudocatenulatum).