Surface proteins are important factors in the interaction of probiotic and pathogenic bacteria with their environment or host. We performed a comparative bioinformatic analysis of four publicly available Lactobacillus genomes and the genome of Lactobacillus salivarius subsp. salivarius strain UCC118 to identify secreted proteins and those linked to the cell wall. Proteins were identified which were predicted to be anchored by WXL-binding domains, N- or C-terminal anchors, GW repeats, lipoprotein anchors, or LysM-binding domains. We identified 10 sortase-dependent surface proteins in L. salivarius UCC118, including three which are homologous to mucus-binding proteins (LSL_0152, LSL_0311, and LSL_1335), a collagen-binding protein homologue (LSL_2020b), two hypothetical proteins (LSL_1838 and LSL_1902b), an enterococcal surface protein homologue (LSL_1085), a salivary agglutinin-binding homologue (LSL_1832b), an epithelial binding protein homologue (LSL_1319), and a proteinase homologue (LSL_1774b). However, two of the genes are gene fragments and four are pseudogenes, suggesting a lack of selection for their function. Two of the 10 genes were not transcribed in vitro, and 1 gene showed a 10-fold increase in transcript level in stationary phase compared to logarithmic phase. The sortase gene was deleted, and three genes encoding sortase-dependent proteins were disrupted. The sortase mutant and one sortase-dependent protein (mucus-binding homologue) mutant showed a significant reduction in adherence to human epithelial cell lines. The genome-wide investigation of surface proteins can thus help our understanding of their roles in host interaction.