Bifidobacteria are colonizers of human gut microbiota, providing better health and nutrition to this ecosystem. Although the beneficial effects of bifidobacteria in human organism are well explored, the molecular interface of this mutualistic relationship remains poor understood. To succeed in colonization and persistence in human gut, bifidobacteria have evolved enzymes to degrade and use complex carbohydrates non-digestible by their hosts. Herein, we report a novel β-mannosidase produced by Bifidobacterium strains for the depolymerization of the ubiquitous 2-acetamido-2-deoxy-4-O-(β-d-mannopyranosyl)-d-glucopyranose (Man-β-1,4-GlcNAc), a disaccharide that composes the universal core of eukaryotic N-glycans. This specialist β-mannosidase contains three distinctive structural elements conferring high selectivity for Man-β-1,4-GlcNAc: a lid that undergoes conformational changes upon substrate binding, a tryptophan residue swapped between the two dimeric subunits to accommodate the GlcNAc moiety, and a Rossmann fold subdomain strategically located near to the active site pocket. These key structural elements for Man-β-1,4-GlcNAc specificity are highly conserved in Bifidobacterium species adapted to the gut of a wide range of social animals, from honey bees to humans. Together, our findings uncover an unprecedented molecular strategy employed by Bifidobacteria to selectively uptake carbohydrates from N-glycans in social hosts.