Human papillomavirus (HPV) vaccines have the potential to prevent cervical cancer by preventing HPV infection or treating premalignant disease. We previously showed that DNA vaccination with the cottontail rabbit papillomavirus (CRPV) E6 gene induced partial protection against CRPV challenge and that the vaccine's effects were greatly enhanced by priming with granulocyte-macrophage colony-stimulating factor (GM-CSF). In the present study, two additional strategies for augmenting the clinical efficacy of CRPV E6 vaccination were evaluated. The first was to fuse a ubiquitin monomer to the CRPV E6 protein to enhance antigen processing and presentation through the major histocompatibility complex class I pathway. Rabbits vaccinated with the wild-type E6 gene plus GM-CSF or with the ubiquitin-fused E6 gene formed significantly fewer papillomas than the controls. The papillomas also required a longer time to appear and grew more slowly. Finally, a significant proportion of the papillomas subsequently regressed. The ubiquitin-fused E6 vaccine was significantly more effective than the wild-type E6 vaccine plus GM-CSF priming. The second strategy was to vaccinate with multiple CRPV early genes to increase the breadth of the CRPV-specific response. DNA vaccines encoding the wild-type CRPV E1-E2, E6, or E7 protein were tested alone and in all possible combinations. All vaccines and combinations suppressed papilloma formation, slowed papilloma growth, and stimulated subsequent papilloma regression. Finally, the two strategies were merged and a combination DNA vaccine containing ubiquitin-fused versions of the CRPV E1, E2, and E7 genes was tested. This last vaccine prevented papilloma formation at all challenge sites in all rabbits, demonstrating complete protection.