Cervical cancer is the third leading cause of female cancers globally, resulting in more than 300,000 deaths every year. The majority of all cervical cancers are caused by persistent infections with high-risk human papillomaviruses (hrHPV) that can progress to cancer via a series of premalignant lesions. Most women, however, clear this infection within a year, concomitant with disease regression. Both hrHPV clearance and disease regression have been associated with the composition of the cervicovaginal microenvironment, which is defined by the host immune system and the cervicovaginal microbiome (CVM). A healthy microbiome is generally characterized by a high abundance of Lactobacillus species, and a change in the composition may cause bacterial vaginosis (BV), which is associated with an increased susceptibility to persistent hrHPV infections and disease. In this review, the composition of the CVM is discussed, with emphasis on the possible causes that drive changes in the cervicovaginal microbiota in relation to hrHPV infections, disease progression, and disease regression. The literature search focused on the composition of the CVM and its correlation with hrHPV infections and neoplastic lesions as well as the current efforts to adjust the microbiome against adverse viral outcomes.