O-GlcNAc is an abundant post-translational modification of serine and threonine residues of nucleocytoplasmic proteins. This modification, found only within higher eukaryotes, is a dynamic modification that is often reciprocal to phosphorylation. In a manner analogous to phosphatases, a glycoside hydrolase termed O-GlcNAcase cleaves O-GlcNAc from modified proteins. Enzymes with high sequence similarity to human O-GlcNAcase are also found in human pathogens and symbionts. We report the three-dimensional structure of O-GlcNAcase from the human gut symbiont Bacteroides thetaiotaomicron both in its native form and in complex with a mimic of the reaction intermediate. Mutagenesis and kinetics studies show that the bacterial enzyme, very similarly to its human counterpart, operates via an unusual 'substrate-assisted' catalytic mechanism, which will inform the rational design of enzyme inhibitors.