To allow vaccination irrespective of HLA type, DNA vaccines encoding full‐length antigens are required. However, here, we demonstrate that the immunogenicity of DNA vaccines encoding the full‐length human papillomavirus (HPV) type 16 E7 and E6 proteins is highly reduced compared to vaccines encoding only the immunodominant epitope. Furthermore, the low remaining immunogenicity is essentially lost for both E7 and E6 when a nononcogenic “gene‐shuffled” variant is utilized. To address these issues, we tested whether alterations in transgene design can restore the immunogenicity of full‐length and gene‐shuffled DNA vaccines. Remarkably, genetic fusion of E7 with tetanus toxin fragment C (TTFC) resulted in a dramatic increase in immunogenicity both for the full‐length and the gene‐shuffled version of E7. Moreover, the TTFC fusion vaccines were more immunogenic than a vaccine encoding a fusion of E7 and mycobacterial heat shock protein‐70, which has recently been tested in a clinical trial. Interestingly, vaccination with these TTFC fusion vaccines also resulted in extremely persistent T‐cell responses. The E7‐specific CD8⁺ T cells induced by TTFC fusion vaccines were functional in terms of IFN‐γ production, formation of immunological memory, in vivo cytolytic activity and tumor eradication. Finally, we show that genetic fusion with TTFC also improves the immunogenicity of a gene‐shuffled E6 DNA vaccine. These data demonstrate that genetic fusion with tetanus toxin fragment C can dramatically improve the immunogenicity of full‐length and gene‐shuffled DNA vaccines. The DNA fusion vaccines developed here will be evaluated for the treatment of HPV‐positive carcinomas in future studies.