Recently, we decoded the genome sequence of Bifidobacterium bifidum PRL2010, an isolate originally recovered from a stool sample of a three month old infant. In silico analysis revealed that the the 2,214,650 bp genome of B. bifidum PRL2010 encoded a rich gene repertoire dedicated to the metabolism of host-derived glycans, such as those present in mucin. Whole proteome profiling as well as transcriptomic investigations were used to identify the genetic players and mechanisms responsible for mucin breakdown, revealing a set of chromosomal loci that allow degradation of various O-linked glycans in mucin (such as core 1, core 2, core 3 and core 4 O-glycans). Comparative genomic analyses involving different B. bifidum genomes demonstrated the ubiquitous presence of these genetic regions in genomes of members of this bifidobacterial taxon, and suggest specific B. bifidum metabolic traits that underpin this case of host-microbe co-evolution.