Glycoside hydrolase family 42 (GH42) includes β-galactosidases catalyzing the release of galactose (Gal) from the non-reducing end of different β-d-galactosides. Health-promoting probiotic bifidobacteria, which are important members of the human gastrointestinal tract microbiota, produce GH42 enzymes enabling utilization of β-galactosides exerting prebiotic effects. However, insight into the specificity of individual GH42 enzymes with respect to substrate monosaccharide composition, glycosidic linkage and degree of polymerization is lagging. Kinetic analysis of natural and synthetic substrates resembling various milk and plant galactooligosaccharides distinguishes the three GH42 members, Bga42A, Bga42B and Bga42C, encoded by the probiotic B. longum subsp. infantis ATCC 15697 and revealed the glycosyl residue at subsite +1 and its linkage to the terminal Gal at subsite −1 to be key specificity determinants. Bga42A thus prefers the β1-3-galactosidic linkage from human milk and other β1-3- and β1-6-galactosides with glucose or Gal situated at subsite +1. In contrast, Bga42B very efficiently hydrolyses 4-galactosyllactose (Galβ1-4Galβ1-4Glc) as well as 4-galactobiose (Galβ1-4Gal) and 4-galactotriose (Galβ1-4Galβ1-4Gal). The specificity of Bga42C resembles that of Bga42B, but the activity was one order of magnitude lower. Based on enzyme kinetics, gene organization and phylogenetic analyses, Bga42C is proposed to act in the metabolism of arabinogalactan-derived oligosaccharides. The distinct kinetic signatures of the three GH42 enzymes correlate to unique sequence motifs denoting specific clades in a GH42 phylogenetic tree providing novel insight into GH42 subspecificities. Overall, the data illustrate the metabolic adaptation of bifidobacteria to the β-galactoside-rich gut niche and emphasize the importance and diversity of β-galactoside metabolism in probiotic bifidobacteria.