Hepatocellular carcinoma (HCC) is the most frequent primary malignancy of the liver in humans. The available anti-HCC therapies are ineffective, and their use has substantial limitations. DNA vaccines expressing α-fetoprotein (AFP), which is a marker of HCC, were recently found to induce the immune response against AFP in vivo. However, the vectors used as vaccines failed to ensure the necessary level of protection, and the immunization procedures were rather complex. We showed earlier that a DNA vaccine encoding HIV-1 reverse transcriptase (RT) with the C end fused with the ornithine decarboxylase (ODC) degradation signal induced a strong Th-1 immune response against RT in mice. In this work, we designed a set of novel DNA vaccines encoding AFP or AFP with the ODC degradation signal. Transfected cells demonstrated efficient expression and fast proteasomal degradation of the recombinant AFP. The antitumor immune response was stimulated in immunized animals, and a notable retardation of HCC growth was observed as a result of protective vaccination.