Many bifidobacteria produce an endo-α- N-acetylgalactosaminidase that liberates the O-linked galactosyl β-1,3N-acetylgalactosamine (GNB) from intestinal mucin glycoproteins. The molecular cloning of the Bifidobacterium longum enzyme was completed using information in public databases. The enzyme constitutes a novel glycoside hydrolase (GH) family 101 member. The gene encoding a specific 1,2-α -L-fucosidase was cloned from B.bifidum. The recombinant enzyme specifically hydrolyzes the terminal α-1,2-fucosidic linkages of various oligosaccharides, including human milk oligosaccharides and blood group substances. Analysis of its primary structure revealed that this enzyme constitutes a novel GH family 95 member. We also solved the crystal structure of its catalytic domain. We assumed that these bifidobacterial enzymes are involved in the metabolism of oligosaccharides in mucin glycoproteins that are abundant in the intestine. Some bifidobacteria strains produce a lacto-N-biosidase that releases galactosyl β-1,3N-acetylglucosamine (LNB) from human milk oligosaccharides, but the other enteric bacteria do not. This disaccharide is one of the building blocks in human milk oligosaccharides and is rarely found in other mammalian milks. The lacto-N-biosidase gene was cloned from B.bifidum and we hypothesized that this enzyme is crucially involved in the degradation of human milk oligosaccharides. The genes encoding sialidase and α-1,3/4-L-fucosidase were also cloned from B.bifidum. These enzymes release modified sialic acid and L-fucose from human milk oligosaccharides, respectively. A solute-binding protein of a putative ABC transporter specific for GNB and LNB was also discovered, and its gene was cloned from B.longum. We named it GNB/LNB-binding protein and crystallized it. Isothermal titration calorimetry measurements revealed that this protein specifically binds GNB and LNB. We speculate that bifidobacteria have a novel GNB/LNB metabolic pathway.