The mucolytic human gut microbiota specialist Akkermansia muciniphila is proposed to boost mucin-secretion by the host, thereby being a key player in mucus turnover. Mucin glycan utilization requires the removal of protective caps, notably fucose and sialic acid, but the enzymatic details of this process remain largely unknown. Here, we describe the specificities of ten A. muciniphila glycoside hydrolases, which collectively remove all known sialyl and fucosyl mucin caps including those on double-sulfated epitopes. Structural analyses revealed an unprecedented fucosidase modular arrangement and explained the sialyl T-antigen specificity of a sialidase of a previously unknown family. Cell-attached sialidases and fucosidases displayed mucin-binding and their inhibition abolished growth of A. muciniphila on mucin. Remarkably, neither the sialic acid nor fucose contributed to A. muciniphila growth, but instead promoted butyrate production by co-cultured Clostridia. This study brings unprecedented mechanistic insight into the initiation of mucin O-glycan degradation by A. muciniphila and nutrient sharing between mucus-associated bacteria.