Lactobacilli are ubiquitous in nature and in humans they play a very significant role in the general health maintenance of the host. Identification of Lactobacilli has previously been based on cultutre-dependent methods and recently molecular techniques involving gene sequencing are now the ‘gold standard’. Scarce information exists in Africa on the real identity of Lactobacillus species, albeit phylogenetic distances among the species present in the human vagina. 185 vaginal swabs were collected from healthy premenopausal women (18-48 years). Bacterial DNA was extracted, amplified using PCR, with group specific 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 ABI prism (3730xl) BigDye Terminator. Phylogenetic tree was constructed with the sequences by the Tree Top-Phylogenetic Tree prediction program. Results shows two distinct divisions among the Lactobacillus species as revealed by the phylogenetic tree. Lactobacillus iners, from both the cluster and topological algorithms, is closely related to L .vaginalis and L. fermentum. L. gasseri, L. suntoryeus, L. johnsonii, L. plantarum, L. rhamnosus, L. crispatus and L. helveticus are closely related in their phylogenetic distances. The study presents a new understanding of the nature of the Lactobacillus vaginal microbiota of women in Nigeria, which may lead to the design of probiotic-lactobacilli for biotherapy.