The vaginal microbiota is thought to play a role in modulating risk of high-risk human papillomavirus (hrHPV) infection. We examined the relationship between the vaginal microbiota and persistent hrHPV infection in HIV-negative and HIV-positive women. We used 16S-rRNA sequencing to characterize the vaginal microbiota of two serial samples taken six months apart from 211 Nigerian women (67%, 142/211 HIV-positive and 33%, 69/211 HIV-negative) and evaluated the association between the vaginal microbiota and persistent hrHPV infection using generalized estimating equation logistic regression models and linear discriminant analysis effect size (LEfSe) algorithm to identify phylotypic biomarkers of persistent hrHPV infection. The high diversity microbiota, Community State Type IV-B, was the most prevalent in both HIV-negative (38% at baseline, 30% at the follow-up visit) and HIV-positive (27% at baseline, 35% at the follow-up visit) women. The relationship between the vaginal microbiota and persistent hrHPV was modified by HIV status. In HIV-negative women, women with Lactobacillus dominant microbiota had lower odds (OR: 0.35, 95% CI 0.14-0.89, p = 0.03) of persistent hrHPV compared to women with Lactobacillus deficient microbiota. While among HIV-positive women, the odds of being persistently infected with hrHPV was higher in women with Lactobacillus dominant microbiota (OR: 1.25, 95% CI 0.73-2.14 p = 0.41). This difference in effect estimates by HIV was statistically significant (p = 0.02). A high diversity vaginal microbial community with paucity of Lactobacillus species was associated with persistent hrHPV infection in HIV-negative women but not in HIV-positive women.