Worldwide the increase in multi-resistant bacteria due to misuse of traditional antibiotics is a growing threat for our health. Finding alternatives to traditional antibiotics is thus timely. Probiotic bacteria have numerous beneficial effects and could offer safer alternatives to traditional antibiotics. Here, we use the nematode Caenorhabditis elegans (C. elegans) to screen a library of different lactobacilli to identify potential probiotic bacteria and characterize their mechanisms of action. We show that pretreatment with the Lactobacillus spp. Lb21 increases lifespan of C. elegans and results in resistance towards pathogenic methicillin-resistant Staphylococcus aureus (MRSA). Using genetic analysis, we find that Lb21-mediated MRSA resistance is dependent on the DBL-1 ligand of the TGF-β signaling pathway in C. elegans. This response is evolutionarily conserved as we find that Lb21 also induces the TGF-β pathway in porcine epithelial cells. We further characterize the host responses in an unbiased proteome analysis and identify 474 proteins regulated in worms fed Lb21 compared to control food. These include fatty acid CoA synthetase ACS-22, aspartic protease ASP-6 and vitellogenin VIT-2 which are important for Lb21-mediated MRSA resistance. Thus, Lb21 exerts its probiotic effect on C. elegans in a multifactorial manner. In summary, our study establishes a mechanistic basis for the antimicrobial potential of lactobacilli.