Bacterial vaginosis (BV) is a polymicrobial imbalance of the vaginal microbiota associated with reproductive infections, preterm birth, and other adverse health outcomes. Sialidase activity in vaginal fluids is diagnostic of BV and sialic acid-rich components of mucus have protective and immunological roles. However, whereas mucus degradation is believed to be important in the etiology and complications associated with BV, the role(s) of sialidases and the participation of individual bacterial species in the degradation of mucus barriers in BV have not been investigated. Here we demonstrate that the BV-associated bacterium Gardnerella vaginalis uses sialidase to break down and deplete sialic acid-containing mucus components in the vagina. Biochemical evidence using purified sialoglycan substrates supports a model in which 1) G. vaginalis extracellular sialidase hydrolyzes mucosal sialoglycans, 2) liberated sialic acid (N-acetylneuraminic acid) is transported into the bacterium, a process inhibited by excess N-glycolylneuraminic acid, and 3) sialic acid catabolism is initiated by an intracellular aldolase/lyase mechanism. G. vaginalis engaged in sialoglycan foraging in vitro, in the presence of human vaginal mucus, and in vivo, in a murine vaginal model, in each case leading to depletion of sialic acids. Comparison of sialic acid levels in human vaginal specimens also demonstrated significant depletion of mucus sialic acids in women with BV compared with women with a "normal" lactobacilli-dominated microbiota. Taken together, these studies show that G. vaginalis utilizes sialidase to support the degradation, foraging, and depletion of protective host mucus barriers, and that this process of mucus barrier degradation and depletion also occurs in the clinical setting of BV.