Peptide-based vaccines aimed at the induction of effective T cell responses against established cancers have so far only met with limited clinical success and clearly need to be improved. In a preclinical model of human papillomavirus (HPV) 16-induced cervical cancer we show that prime-boost vaccinations with the HPV16-derived 35 amino-acid long peptide E7 43–77, containing both a CTL epitope and a Th epitope, resulted in the induction of far more robust E7-specific CD8+ T cell responses than vaccinations with the minimal CTL epitope only. We demonstrate that two distinct mechanisms are responsible for this effect. First, vaccinations with the long peptide lead to the generation of E7-specific CD4+ Th cells. The level of the induced E7-specific CD8+ T cell response proved to be dependent on the interactions of these Th cells with professional APC. Second, we demonstrate that vaccination with the long peptide and dendritic cell-activating agents resulted in a superior induction of E7-specific CD8+ T cells, even when T cell help was excluded. This suggests that, due to its size, the long peptide was preferably endocytosed, processed, and presented by professional APCs. Moreover, the efficacy of this superior HPV-specific T cell induction was demonstrated in therapeutic prime-boost vaccinations in which the long peptide admixed with the dendritic cell-activating adjuvant oligodeoxynucleotide-CpG resulted in the eradication of large, established HPV16-expressing tumors. Because the vaccine types used in this study are easy to prepare under good manufacturing practice conditions and are safe to administer to humans, these data provide important information for future clinical trials.