We have previously shown that a novel DNA vaccine technology of codon optimization and the addition of ubiquitin sequences enhanced immunogenicity of a herpes simplex virus 2 polynucleotide vaccine in mice, and induced cell-mediated immunity when administered in humans at relatively low doses of naked DNA. We here show that a new polynucleotide vaccine using the same technology and encoding a fusion protein of the E6 and E7 oncogenes of high-risk human papillomavirus type 16 (HPV16) is immunogenic in mice. This vaccine induces long-lasting humoral and cell-mediated immunity and protects mice from establishment of HPV16-E7-expressing tumors. In addition, it suppresses growth of readily established tumors and shows enhanced efficacy when combined with immune checkpoint blockade targeted at PD-L1. This vaccine also facilitates rejection of HPV16-E7-expressing skin grafts that demonstrate epidermal hyperplasia with characteristics of cervical and vulvar intraepithelial neoplasia. Clinical studies evaluating the efficacy of this vaccine in patients with HPV16+ premalignancies are planned.