Antibody modulation of T-cell coinhibitory (e.g., CTLA-4) or costimulatory (e.g., 4-1BB) receptors promotes clinical responses to a variety of cancers. Therapeutic cancer vaccination, in contrast, has produced limited clinical benefit and no curative therapies. The E6 and E7 oncoproteins of human papilloma virus (HPV) drive the majority of genital cancers, and many oropharyngeal tumors. We discovered 15-19 amino acid peptides from HPV-16 E6/E7 for which induction of T-cell immunity correlates with disease-free survival in patients treated for high-grade cervical neoplasia. We report here that intranasal vaccination with these peptides and the adjuvant alpha-galactosylceramide elicits systemic and mucosal T-cell responses leading to reduced HPV(+) TC-1 tumor growth and prolonged survival in mice. We hypothesized that the inability of these T cells to fully reject established tumors resulted from suppression in the tumor microenvironment which could be ameliorated through checkpoint modulation. Combining this E6/E7 peptide vaccine with checkpoint blockade produced only modest benefit; however, coadministration with a 4-1BB agonist antibody promoted durable regression of established genital TC-1 tumors. Relative to other therapies tested, this combination of vaccine and α4-1BB promoted the highest CD8(+) versus regulatory FoxP3(+) T-cell ratios, elicited 2- to 5-fold higher infiltration by E7-specific CTL, and evoked higher densities of highly cytotoxic TcEO (T cytotoxic Eomesodermin) CD8 (>70-fold) and ThEO (T helper Eomesodermin) CD4 (>17-fold) T cells. These findings have immediate clinical relevance both in terms of the direct clinical utility of the vaccine studied and in illustrating the potential of 4-1BB antibody to convert therapeutic E6/E7 vaccines already in clinical trials into curative therapies.