Bacterial vaginosis (BV) is the most common vaginal syndrome afflicting fertile, premenopausal and pregnant women. BV is associated with important adverse health conditions and infectious complications. Therapy with oral or local recommended antibiotics is often associated with failure and high rates of recurrences. The dominance of lactobacilli in healthy vaginal microbiota and its depletion in BV has given rise to the concept of oral or vaginal use of probiotic Lactobacillus strains for treatment and prevention of BV. This review investigated the evidence for the use of a single strain or cocktail of probiotics, administered orally or intravaginally, either alone or in conjunction with antibiotics for the treatment of BV. Lactobacilli use in BV is supported by positive results obtained in some clinical trials. The majority of clinical trials yielding positive results have been performed using probiotic preparations containing high doses of lactobacilli suggesting that, beside strain characteristics, the amount of exogenously applied lactobacilli could have a role in the effectiveness of the product. However, substantial heterogeneity in products, trial methodologies and outcome measures do not provide sufficient evidence for or against recommending probiotics for the treatment of BV.