Background: Bacterial vaginosis (BV) is a common cause of vaginal discharge and associated with vaginal acquisition of BV-Associated bacteria (BVAB). Methods: We used quantitative polymerase chain reaction assays to determine whether presence or concentrations of BVAB in the mouth, anus, vagina, or labia before BV predict risk of incident BV in 72 women who have sex with men. Results: Baseline vaginal and extra-vaginal colonization with Gardnerella spp, Megasphaera spp, Sneathia spp, BVAB-2, Dialister sp type 2, and other BVAB was more common among subjects with incident BV. Conclusions: Prior colonization with BVAB is a consistent risk for BV.