Infant gut-associated bifidobacteria possess species-specific enzymatic sets to assimilate human milk oligosaccharides, and lacto-N-biosidase (LNBase) is a key enzyme that degrades lacto-N-tetraose (Galβ1-3GlcNAcβ1-3Galβ1-4Glc), the main component of human milk oligosaccharides, to lacto-N-biose I (Galβ1-3GlcNAc) and lactose. We have previously identified LNBase activity in Bifidobacterium bifidum and some strains of Bifidobacterium longum subsp. longum (B. longum). Subsequently, we isolated a glycoside hydrolase family 20 (GH20) LNBase from B. bifidum; however, the genome of the LNBase(+) strain of B. longum contains no GH20 LNBase homolog. Here, we reveal that locus tags BLLJ_1505 and BLLJ_1506 constitute LNBase from B. longum JCM1217. The gene products, designated LnbX and LnbY, respectively, showed no sequence similarity to previously characterized proteins. The purified enzyme, which consisted of LnbX only, hydrolyzed via a retaining mechanism the GlcNAcβ1-3Gal linkage in lacto-N-tetraose, lacto-N-fucopentaose I (Fucα1-2Galβ1-3GlcNAcβ1-3Galβ1-4Glc), and sialyllacto-N-tetraose a (Neu5Acα2-3Galβ1-3GlcNAcβ1-3Galβ1-4Gal); the latter two are not hydrolyzed by GH20 LNBase. Among the chromogenic substrates examined, the enzyme acted on p-nitrophenyl (pNP)-β-lacto-N-bioside I (Galβ1-3GlcNAcβ-pNP) and GalNAcβ1-3GlcNAcβ-pNP. GalNAcβ1-3GlcNAcβ linkage has been found in O-mannosyl glycans of α-dystroglycan. Therefore, the enzyme may serve as a new tool for examining glycan structures. In vitro refolding experiments revealed that LnbY and metal ions (Ca(2+) and Mg(2+)) are required for proper folding of LnbX. The LnbX and LnbY homologs have been found only in B. bifidum, B. longum, and a few gut microbes, suggesting that the proteins have evolved in specialized niches.