High-risk human papillomavirus (HPV) are responsible for genital and oral cancers associated with the expression of the E6/E7 HPV oncogenes. Therapeutic vaccines targeting those oncogenes can only partially control tumor progression, highlighting the necessity to investigate different treatment strategies. Using the genital orthotopic HPV16 TC-1 model, herein we sequentially investigated in progressively more stringent settings the effects of systemic administration of carboplatin/paclitaxel (C + P) chemotherapy combined with HPV16-E7 synthetic long peptide (E7LP) vaccination, followed by intravaginal immunostimulation with the synthetic toll-like-receptor-9 agonist CpG. Our data show that systemic delivery of C + P prior to E7LP vaccination significantly increased mice survival. This survival benefit was associated with both reduced genital tumor growth at the time of vaccination, and a decreased infiltration of Ly6G myeloid cells and tumor-associated macrophages. Adding intravaginal CpG, which results in increased E7-specific CD8 T cells locally, to E7LP vaccination and the chemotherapy formed a tri-therapy, which significantly increased mice survival as compared to any of the dual treatments. When the tri-therapy was further refined by using a recently optimized nanoparticle-conjugated E7LP vaccine, even larger end-stage genital-TC-1 tumors responded, with 90% of mice showing a survival benefit as compared to 30% of mice with the tri-therapy involving the traditional E7LP 'liquid' vaccine. C + P is commonly used to treat cervical cancer patients and its combination with E7/E6 vaccination is currently being tested in a phase I/II trial (NCT02128126). Our data suggests that new vaccine formulations combined with local immunostimulation and standard-of-care chemotherapy have promise to further benefit patients with HPV-associated cancer.