Bifidobacterium longum endo-α-N-acetylgalactosaminidase (GH101), EngBF, is highly specific toward the mucin Core 1 glycan, Galβ1-3GalNAc. Apart from the side chains involved in the retaining mechanism of EngBF, Asp-682 is important for the activity. In the crystal structures of both EngBF and EngSP (from Streptococcus pneumoniae), we identified a conserved water molecule in proximity to Asp-682 and the homologue residue in EngSP. The water molecule also coordinates the catalytic nucleophile and three other residues conserved in GH101 enzymes; in EngBF, these residues are His-685, His-718, and Asn-720. With casein-glycomacropeptide as the substrate, the importance of Asp-682 was confirmed by the lack of a detectable activity for the D682N enzyme. The enzyme variants, H685A, H718A, H685Q, and H718Q, all displayed only a modestly reduction in kcat of up to 15 fold for the H718A variant. However, the double-substituted variants, H685A/H718A and H685Q/H718Q, had a greatly reduced kcat value by about 200 fold compared to that of wild-type EngBF. With the synthetic substrate, Galβ(1-3)GalNAcα1-para-nitrophenol, kcat of the double-substituted variants was only up to 30-fold reduced and was found to increase with pH. Compared to the pre-steady-state kinetics of wild-type EngBF, a burst of about the size of the enzyme concentration was absent with the double-substituted EngBF variants, indicating that the nucleophilic attack had become at least as slow as the hydrolysis of the enzyme intermediate. Together, the results indicate that not only Asp-682 but also the entire conserved network of His-685, His-718, and what we suggest is a catalytic water molecule is important in the activation of the catalytic nucleophile.