Updated project metadata. Akkermansia muciniphila, a mucin-degrading microbe found in the human gut, is often associated with positive health outcomes. The abundance of Akkermansia muciniphila is modulated by the presence and accessibility of nutrients, which can be derived from diet or host glycoproteins. In particular, the ability to degrade host mucins, a class of proteins carrying densely O-glycosylated domains, provides a competitive advantage in the sustained colonization of niche mucosal environments. Although Akkermansia muciniphila is known to rely on mucins as a carbon and nitrogen source, the enzymatic machinery used by this microbe to process mucins in the gut is not yet fully characterized. Here, we focus on the mucin-selective metalloprotease, Amuc_0627 (AM0627), which is known to cleave between adjacent residues carrying truncated core 1 O-glycans. We showed that this enzyme is capable of degrading purified mucin 2 (MUC2), the major protein component of mucus in the gut. An X-ray crystal structure of AM0627 at 1.9 Å resolution revealed O-glycan binding residues that are conserved between structurally characterized enzymes from the same family. We further rationalized the substrate cleavage motif using molecular modeling to identify nonconserved glycan-interacting residues. Mutagenesis of these residues resulted in altered substrate preferences down to the glycan level, providing insight into the structural determinants of O-glycan recognition.