The breast-fed infant intestine is often colonized by particular bifidobacteria, and human milk oligosaccharides (HMOs) are considered to be bifidogenic. Recent studies showed that Bifidobacterium longum subsp. infantis can grow on HMOs as the sole carbon source. This ability has been ascribed to the presence of a gene cluster (HMO cluster-1) contained in its genome. However, the metabolism of HMOs by the organism remains unresolved because no enzymatic studies have been completed. In the present study, we characterized β-galactosidases of this subspecies to understand how the organism degrades type-1 (Galβ1-3GlcNAc) and type-2 (Galβ1-4GlcNAc) isomers of HMOs. The results revealed that the locus tag Blon_2016 gene, which is distantly located from the HMO cluster-1, encodes a novel β-galactosidase (Bga42A) with a significantly higher specificity for lacto-N-tetraose (LNT; Galβ1-3GlcNAcβ1-3Galβ1-4Glc) than for lacto-N-biose I (Galβ1-3GlcNAc), lactose (Lac) and type-2 HMOs. The proposed name of Bga42A is LNT β-1,3-galactosidase. The Blon_2334 gene (Bga2A) located within the HMO cluster-1 encodes a β-galactosidase specific for Lac and type-2 HMOs. Real-time quantitative reverse transcription–polymerase chain reaction analysis revealed the physiological significance of Bga42A and Bga2A in HMO metabolism. The organism therefore uses two different β-galactosidases to selectively degrade type-1 and type-2 HMOs. Despite the quite rare occurrence in nature of β-galactosidases acting on type-1 chains, the close homologs of Bga42A were present in the genomes of infant-gut associated bifidobacteria that are known to consume LNT. The predominance of type-1 chains in HMOs and the conservation of Bga42A homologs suggest the coevolution of these bifidobacteria with humans.