Abstract Human gut symbiont bifidobacteria possess carbohydrate-degrading enzymes that act on the O-linked glycans of intestinal mucins to utilize those carbohydrates as carbon sources. However, our knowledge about mucin type O-glycan degradation by bifidobacteria remains fragmentary, especially regarding how they decompose sulfated glycans, which are abundantly found in mucin sugar-chains. Here, we examined the abilities of several Bifidobacterium strains to degrade a sulfated glycan substrate and identified a 6-sulfo-β-d-N-acetylglucosaminidase, also termed sulfoglycosidase, encoded by bbhII from Bifidobacterium bifidum JCM 7004. A recombinant BbhII protein showed a substrate preference toward 6-sulfated and 3,4-disulfated N-acetylglucosamines over non-sulfated and 3-sulfated N-acetylglucosamines. The purified BbhII directly released 6-sulfated N-acetylglucosamine from porcine gastric mucin and the expression of bbhII was moderately induced in the presence of mucin. This de-capping activity may promote utilization of sulfated glycans of mucin by other bacteria including bifidobacteria, thereby establishing the symbiotic relationship between human and gut microbes.