The Bifidobacterium genus harbours several health promoting members of the gut microbiota. Bifidobacteria display metabolic specialization by preferentially utilizing dietary or host-derived β-galactosides. This study investigates the biochemistry and structure of a glycoside hydrolase family 42 (GH42) β-galactosidase from the probiotic Bifidobacterium animalis subsp. lactis Bl-04 (BlGal42A). BlGal42A displays a preference for undecorated β1-6 and β1-3 linked galactosides and populates a phylogenetic cluster with close bifidobacterial homologues implicated in the utilization of N-acetyl substituted β1-3 galactosides from human milk and mucin. A long loop containing an invariant tryptophan in GH42, proposed to bind substrate at subsite + 1, is identified here as specificity signature within this clade of bifidobacterial enzymes. Galactose binding at the subsite − 1 of the active site induced conformational changes resulting in an extra polar interaction and the ordering of a flexible loop that narrows the active site. The amino acid sequence of this loop provides an additional specificity signature within this GH42 clade. The phylogenetic relatedness of enzymes targeting β1-6 and β1-3 galactosides likely reflects structural differences between these substrates and β1-4 galactosides, containing an axial galactosidic bond. These data advance our molecular understanding of the evolution of sub-specificities that support metabolic specialization in the gut niche.