CAZy glycoside hydrolase family GH3 consists primarily of stereochemistry-retaining β-glucosidases but also contains a subfamily of β-N-acetylglucosaminidases. Enzymes from this subfamily were recently shown to use a histidine residue within a His-Asp dyad contained in a signature sequence as their catalytic acid/base residue. Reasons for their use of His rather than the Glu or Asp found in other glycosidases were not apparent. Through studies on a representative member, the Nag3 β-N-acetylglucosaminidase from Cellulomonas fimi, we now show that these enzymes act preferentially as glycoside phosphorylases. Their need to accommodate an anionic nucleophile within the enzyme active site explains why histidine is used as an acid/base catalyst in place of the anionic glutamate seen in other GH3 family members. Kinetic and mechanistic studies reveal that these enzymes also employ a double-displacement mechanism involving a covalent glycosyl-enzyme intermediate, which was directly detected by mass spectrometry. Phosphate has no effect on the rates of formation of the glycosyl-enzyme intermediate, but it accelerates turnover of the N-acetylglucosaminyl-enzyme intermediate ∼3-fold, while accelerating turnover of the glucosyl-enzyme intermediate several hundredfold. These represent the first reported examples of retaining β-glycoside phosphorylases, and the first instance of free β-GlcNAc-1-phosphate in a biological context.