Lactobacilli are involved in the microbial homeostasis in the female genital tract. Due to the high prevalence of many bacterial diseases of the female genital tract and the resistance of microorganisms to various antimicrobial agents, alternative means to control these infections are necessary. Thus, this study aimed to evaluate the probiotic properties of well-characterized Lactobacillus species, including L. acidophilus (ATCC 4356), L. brevis (ATCC 367), L. delbrueckii ssp. delbrueckii (ATCC 9645), L. fermentum (ATCC 23271), L. paracasei (ATCC 335), L. plantarum (ATCC 8014), and L. rhamnosus (ATCC 9595), against Candida albicans (ATCC 18804), Neisseria gonorrhoeae (ATCC 9826), and Streptococcus agalactiae (ATCC 13813). The probiotic potential was investigated by using the following criteria: i) adhesion to host epithelial cells and mucus, ii) biofilm formation, iii) co-aggregation with bacterial pathogens, iv) inhibition of pathogen adhesion to mucus and HeLa cells, and v) antimicrobial activity. Tested lactobacilli adhered to mucin, co-aggregated with all genital microorganisms, and displayed antimicrobial activity. With the exception of L. acidophilus and L. paracasei, they adhered to HeLa cells. However, only L. fermentum produced a moderate biofilm and a higher level of co-aggregation and mucin binding. The displacement assay demonstrated that all Lactobacillus strains inhibit C. albicans binding to mucin (p < 0.001), likely due to the production of substances with antimicrobial activity. Clinical isolates belonging to the most common Candida species associated to vaginal candidosis were inhibited by L. fermentum. Collectively, our data suggest that L. fermentum ATCC 23271 is a potential probiotic candidate, particularly to complement candidosis treatment, since presented with the best probiotic profile in comparison with the other tested lactobacilli strains.