Lactobacilli strains are considered as a preventive means for treatment of vaginal infections or post-antibiotic treatment to repopulate the vaginal mucosa. This study aimed at establishing the vaginal lactobacillus profile of Algerian women with different vaginal diseases. Afterwards, lactobacilli isolated from swabs were in vitro characterized for their probiotic hallmarks. This prospective study allowed isolation of 44 Lactobacillus strains and 160 potentially pathogens, among which are Escherichia coli (50 isolates), Staphylococcus sp. (38 isolates), Enterococcus sp. (16 isolates), and Candida sp. (56 isolates). All Lactobacilli strains were characterized for their antagonism, adhesion to polystyrene, and resistance to acidity and bile. Consequently, six Lactobacillus strains (Lb. fermentum 5LB4, 5LB10, 5LB12, Lb. plantarum 5LB2, 5LB11, and Lactobacillus sp. 4LB9) were moderately or weakly adherent, and 35 potentially pathogens exhibited weak to strong adhesion to polystyrene. Antagonism was recorded for 36 Lactobacillus strains towards E. coli 6E2, S. aureus 7S3, Enterococcus sp. 5EN8, and Candida albicans C1 used as indicator organisms. Finally, Lb. fermentum 9LB6, 4LB16, and 10LB1 and Lb. plantarum 9LB4 were remarkable for their inhibitory activity, absence of hemolytic potential, and for their resistance to acidity (pH1.5) and bile (0.5%) harsh conditions.