Probiotic bacteria including Bifidobacterial species have the capacity to improve intestinal health, but the underlying molecular mechanisms are often not understood. Bifidobacteria are considered keystone species but have a relatively low abundance in the adult intestinal tract. Bifidobacterium colonization depends on degradation of host-derived carbohydrates, including human milk oligosaccharides and mucin-associated oligosaccharides. Specific Bifidobacterium strains can enhance intestinal barrier integrity and improve symptoms of gastrointestinal disorders. We previously reported that the transmembrane mucin MUC13 localizes to the apical and lateral membrane and regulates epithelial tight junction strength. Here, we screened probiotic bacterial strains for their capacity to modulate MUC13 and enhance intestinal barrier function. Of these probiotic bacteria, a Bifidobacterium bifidum strain uniquely degraded the MUC13 O-glycosylated extracellular domain. Further characterization of two probiotic B. bifidum strains (W23 and W28) and the type strain 20456 demonstrated that the W23 and W28 strains adhered strongly to the apical surface, had high sialidase activity, penetrated the mucus layer, and enhanced epithelial barrier integrity. These results underscore the strain-specific properties of these specific B. bifidum strains that most likely contribute to their probiotic effects in the intestinal tract.