Bacterial vaginosis (BV) is particularly common in black women, and in Nigeria it is often caused by Mycoplasma, as well as Atopobium, Prevotella and Gardnerella sp. Antimicrobial metronidazole oral therapy is poorly effective in eradicating the condition and restoring the Lactobacillus microbiota in the vagina. In this study, 40 women diagnosed with BV by discharge, fishy odor, sialidase positive test and Nugent Gram stain scoring, were randomized to receive either two dried capsules containing Lactobacillus rhamnosus GR-1 and L. reuteri RC-14 each night for five days, or 0.75% metronidazole gel, applied vaginally twice a day (in the morning and evening). Follow-up at day 6, 15 and 30 showed cure of BV in significantly more probiotic treated subjects (16, 17 and 18/20 respectively) compared to metronidazole treatment (9, 9 and 11/20: P= 0.016 at day 6, P= 0.002 at day 15 and P= 0.056 at day 30). This is the first report of an effective (90%) cure of BV using probiotic lactobacilli. Given the correlation between BV and HIV, and the high risk of the latter in Nigeria, intravaginal use of lactobacilli could provide women with a self-use therapy, similar to over-the-counter anti-yeast medication, for treatment of urogenital infections.