Sortases are a class of enzymes that anchor surface proteins to the cell wall of Gram-positive bacteria. Lactobacillus casei BL23 harbors four sortase genes, two belonging to class A (srtA1 and srtA2) and two belonging to class C (srtC1 and srtC2). Class C sortases were clustered with genes encoding their putative substrates that were homologous to the SpaEFG and SpaCBA proteins that encode mucus adhesive pili in Lactobacillus rhamnosus GG. Twenty-three genes encoding putative sortase substrates were identified in the L. casei BL23 genome with unknown (35%), enzymatic (30%), or adhesion-related (35%) functions. Strains disrupted in srtA1, srtA2, srtC1, and srtC2 and an srtA1 srtA2 double mutant were constructed. The transcription of all four sortase encoding genes was detected, but only the mutation of srtA1 resulted in a decrease in bacterial surface hydrophobicity. The β-N-acetyl-glucosaminidase and cell wall proteinase activities of whole cells diminished in the srtA1 mutant and, to a greater extent, in the srtA1 srtA2 double mutant. Cell wall anchoring of the staphylococcal NucA reporter protein fused to a cell wall sorting sequence was also affected in the srtA mutants, and the percentages of adhesion to Caco-2 and HT-29 intestinal epithelial cells were reduced for the srtA1 srtA2 strain. Mutations in srtC1 or srtC2 result in an undetectable phenotype. Together, these results suggest that SrtA1 is the housekeeping sortase in L. casei BL23 and SrtA2 would carry out redundant or complementary functions that become evident when SrtA1 activity is absent.