α-Linked N-acetylglucosamine is one of the major glyco-epitopes in O-glycan of gastroduodenal mucin. Here, we identified glycoside hydrolase (GH) family 89 α-N-acetylglucosaminidase, termed AgnB, from Bifidobacterium bifidum JCM 1254, which is essentially specific to GlcNAcα1-4Gal structure. AgnB is a membrane-anchored extracellular enzyme consisting of a GH89 domain and four carbohydrate-binding module (CBM) 32 domains. Among four CBM32 domains, three tandem ones at C-terminus showed to bind porcine gastric mucin, suggesting that these domains enhance the enzyme activity by increasing affinity for multivalent substrates. AgnB might be important for assimilation of gastroduodenal mucin by B. bifidum and also applicable to production of prebiotic oligosaccharides from porcine gastric mucin.