Loss of immunogenic epitopes by tumors has urged the development of vaccines against multiple epitopes. Recombinant DNA technologies have opened the possibility to develop multiepitope vaccines in a relatively rapid and efficient way. We have constructed four naked DNA-based multiepitope vaccines, containing CTL, Th cell, and B cell epitopes of the human papillomavirus type 16. Here we show that gene gun-mediated vaccination with an epitope-based DNA vaccine protects 100% of the vaccinated mice against a lethal tumor challenge. The addition of spacers between the epitopes was crucial for the epitope-induced tumor protection, as the same DNA construct without spacers was significantly less effective and only protected 50% of the mice. When tested for therapeutic potential, only the epitope construct with defined spacers significantly reduced the size of established tumors, but failed to induce tumor regression. Only after targeting the vaccine-encoded protein to the protein degradation pathway by linking it to ubiquitin, the vaccine-induced T cell-mediated eradication of 100% of 7-day established tumors in mice. The finding that defined flanking sequences around epitopes and protein targeting dramatically increased the efficacy of epitope string DNA vaccines against established tumors will be of importance for the further development of multiepitope DNA vaccines toward clinical application.