The primary objective of this study was to investigate if supplementary lactobacilli treatment could improve the initial cure rate after vaginal clindamycin therapy, and secondly, if lactobacilli as repeated adjunct treatment during 3 menstrual cycles could lengthen the time to relapse after initial cure. Women (n = 100) with bacterial vaginosis diagnosed by Amsel criteria were after informed consent offered vaginal clindamycin therapy followed by vaginal gelatine capsules containing either 109 freeze-dried lactobacilli or identical placebo capsules for 10 days during 3 menstrual cycles in a double-blind, randomized, placebo-controlled trial. The initial intent to treat (ITT) analysis for the one-month cure rate was 64% in the lactobacilli group and 78% in the placebo group (p > 0.05). However, any patient with missing or unclassified smears at the initial visit who continued the study and whose next smear indicated a cure was included in the cured group; the study also excluded two of the patients in the lactobacilli group who reported that they did not take any vaginal capsules. With consideration to these population changes, the initial cure rate would be 77% in the lactobacilli group. The 76 cured women were followed for 6 menstrual cycles or until relapse within that time span. At the end of the study, 64.9% (24/37) of the lactobacilli treated women were still BV-free compared to 46.2% (18/39) of the placebo treated women. Comparison of the two groups regarding "Time from cure to relapse" was statistically significant (p = 0.027) in favour of the lactobacilli treatment. Adjuvant therapy with lactobacilli contributed significantly to avoidance of relapse with a proportional Hazard Risk ratio (HR) of 0.73 (0.54–0.98) (p < 0.05) The study shows that supplementary treatment combining two different strains of probiotic lactobacilli does not improve the efficacy of BV therapy during the first month of treatment, but for women initially cured, adjunct treatment of lactobacilli during 3 menstrual cycles lengthens the time to relapse significantly in that more women remained BV free at the end of the 6-month follow up. ISRCTN62879834