Lactobacilli belong to the lactic acid bacteria, which play a key role in industrial and artisan food raw-material fermentation, including a large variety of fermented dairy products. Next to their role in fermentation processes, specific strains of Lactobacillus are currently marketed as health-promoting cultures or probiotics. The last decade has witnessed the completion of a large number of Lactobacillus genome sequences, including the genome sequences of some of the probiotic species and strains. This development opens avenues to unravel the Lactobacillus-associated health-promoting activity at the molecular level. It is generally considered likely that an important part of the Lactobacillus effector molecules that participate in the proposed health-promoting interactions with the host (intestinal) system resides in the bacterial cell envelope. For this reason, it is important to accurately predict the Lactobacillus exoproteomes. Extensive annotation of these exoproteomes, combined with comparative analysis of species- or strain-specific exoproteomes, may identify candidate effector molecules, which may support specific effects on host physiology associated with particular Lactobacillus strains. Candidate health-promoting effector molecules of lactobacilli can then be validated via mutant approaches, which will allow for improved strain selection procedures, improved product quality control criteria and molecular science-based health claims.