Abstract: The search for Lactobacilli of African origin with probiotic properties formed the basis of the study. Two hundred and forty one premenopausal healthy (as defined by having no symptoms of vaginal infections and are HIV negative) Nigerian women provided vaginal swabs. The swabs were cultured on de Man Rogosa Sharpe (MRS) agar (pH 5.5) and incubated anaerobically at 37°C for 48 h. Microbial DNA was extracted from the colonies and directly from the swabs, amplified using Polymerase Chain Reaction (PCR) with Lactobacillus primers and processed by Denaturing Gradient Gel Electrophoresis (DGGE). DGGE bands were excised, re-amplified, purified, V2-V3 region of 16S rRNA gene sequenced with 3730xl ABI prism BigDye Terminator and sequence identification was by BLAST. Lactobacillus strains were tested for probiotic properties (H2O2, Pathogen inhibition and Biosurfactant production). Out of 241 swab samples cultured on MRS agar, only 24 (10%) samples had growth of Lactobacillus species at pH 4.5. Lactobacillus gasseri was isolated from 6 (3.3%)samples, followed by L. plantarum (2.4%), L. vaginalis (1.6%), L. fermentum (0.8%), L. crispatus (0.8%) and L. rhamnosus (0.8%). Two species, each of Lactobacillus plantarum and L. fermentum produced huge amount of biosurfactants. In addition they produced H2O2, inhibited the growth of intestinal and urogenital pathogens. The study presents a new understanding by culture method showing lactobacilli composition of the vagina of some Nigerian women. Two Lactobacillus species exhibited probiotic characteristics and clinical studies with these strains are now planned following investigation of the genomic regions encoding probiotic functionality.