Human papillomavirus (HPV) infections are the main cause of cervical and oropharyngeal cancers. As prophylactic vaccines have no curative effect, an efficient therapy would be highly desired. Most therapeutic vaccine candidates target only a small subset of HPV regulatory proteins, namely, E6 and E7, and are therefore restricted in the breadth of their immune response. However, research has suggested E1 and E2 as promising targets to fight HPV+ cancer. Here, we report the design of adenoviral vectors efficiently expressing HPV16 E1 and E2 in addition to transformation-deficient E6 and E7. Vaccination elicited vigorous CD4+ and CD8+ T-cell responses against all encoded HPV16 proteins in outbred mice and against E1 and E7 in C57BL/6 mice. Therapeutic vaccination of C3 tumor-bearing mice led to significantly reduced tumor growth and enhanced survival for both small and established tumors. Tumor biopsies revealed increased numbers of tumor-infiltrating CD8+ T cells in treated mice. Cisplatin enhanced the effect of therapeutic vaccination, accompanied by enhanced infiltration of dendritic cells into the tumor. CD8+ T cells were identified as effector cells in T-cell depletion assays, seemingly under regulation by FoxP3+CD4+ regulatory T cells. Finally, therapeutic vaccination with Ad-Ii-E1E2E6E7 exhibited significantly enhanced survival compared with vaccination with two peptides each harboring a known E6/E7 epitope. We hypothesize that this difference could be due to the induction of additional T-cell responses against E1. These results support the use of this novel vaccine candidate targeting an extended set of antigens (Ad-Ii-E1E2E6E7), in combination with cisplatin, as an advanced strategy to combat HPV+ cancers.