Microbes utilize polysaccharides to protect their surfaces and build biofilms, whereas metazoans employ large mucins densely decorated with _O_-glycans to protect surfaces and keep microbes at a distance. However, gut microbes in mucus also feed on host mucins, thus imposing a need for continuous renewal to maintain protection, clearance and mucus homeostasis. Glycopeptidases that can cleave mucins are known, but mucinases that specifically cleave mucins are not. Here we report the discovery of such microbial mucinases that cleave mucins with trimmed glycans, recognize dense clusters of _O_-glycans, and employ a structural fold and catalytic machinery reminiscent of glycan hydrolases and peptidases. These di-glutamate mucinases are also found in eukaryotes, and we propose that they are designed to clear mucins following scavenging of _O_-glycans to promote healthy gut-microbiome homeostasis.