Endo-alpha-N-acetylgalactosaminidase (endo-alpha-GalNAc-ase), a member of the glycoside hydrolase (GH) family 101, hydrolyses the O-glycosidic bonds in mucin-type O-glycan between alpha-GalNAc and Ser/Thr. Endo-alpha-GalNAc-ase from Bifidobacterium longum JCM1217 (EngBF) is highly specific for the core 1-type O-glycan to release the disaccharide Galbeta1-3GalNAc (GNB), whereas endo-alpha-GalNAc-ase from Clostridium perfringens (EngCP) exhibits broader substrate specificity. We determined the crystal structure of EngBF at 2.0 A resolution and performed automated docking analysis to investigate possible binding modes of GNB. Mutational analysis revealed important residues for substrate binding, and two Trp residues (Trp748 and Trp750) appeared to form stacking interactions with the beta-faces of sugar rings of GNB by substrate-induced fit. The difference in substrate specificities between EngBF and EngCP is attributed to the variations in amino acid sequences in the regions forming the substrate-binding pocket. Our results provide a structural basis for substrate recognition by GH101 endo-alpha-GalNAc-ases and will help structure-based engineering of these enzymes to produce various kinds of neo-glycoconjugates.