We assessed the association between recent bacterial vaginosis (BV) and incident Mycoplasma genitalium, a sexually transmitted bacterium associated with adverse female reproductive health outcomes. Female sex workers in Mombasa, Kenya, completed a monthly sexual behavior interview and clinical examination. During February 2005–February 2006, vaginal fluid specimens collected from women every other month were tested for M. genitalium by nucleic acid amplification testing. Vaginal microbiota were assessed monthly and categorized by Nugent score (0–3 = normal microbiota, 4–6 = intermediate microbiota disruption, and 7–10 = BV). A discrete failure time analysis for multiple events using logistic regression was employed to estimate the odds of incident M. genitalium infection at follow-up visits among women with BV (vs. normal microbiota) at the preceding visit. Among the 280 women, 54.3% were positive for human immunodeficiency virus. At baseline, 16.1% had prevalent M. genitalium infection and 40.4% had prevalent BV. There were 59 incident M. genitalium infections among 50 women, for an incidence rate of 34.6 cases per 100 person-years. Following adjustment for age, human immunodeficiency virus status, and time, prior BV was associated with a 3.5-fold increase in odds of incident M. genitalium (adjusted odds ratio = 3.49, 95% confidence interval: 1.86, 6.56). This strong association suggests that BV may enhance susceptibility to M. genitalium infection.