Human papillomavirus (HPV) infection is a major cause of cervical cancer, the second most common cancer in women worldwide. Currently, a HPV L1-based virus-like particle has been approved as a prophylactic vaccine against HPV infection, which will probably lead to a reduction in cervical cancer incidence within a few decades. Therapeutic vaccines, however, are expected to have an impact on cervical cancer or its precursor lesions, by taking advantage of the fact that the regulatory proteins (E6 and E7) of HPV are expressed constantly in HPV-associated cervical cancer cells. Vaccine types targeting these regulatory proteins include the recombinant protein and DNA vaccines, peptide vaccines, dendritic-cell vaccines, and viral and bacterial vector deliveries of vaccines, and these may provide an opportunity to control cervical cancer. Further approaches incorporating these vaccine types with either conventional therapy modalities or the modulation of CD4(+) regulatory T cells appear to be more promising in achieving increased therapeutic efficacy. In this review, we summarize current and future therapeutic vaccine strategies against HPV-associated malignancies at the animal and clinical levels.