Antitumor vaccination therapy approaches using naked plasmid DNA or recombinant viruses encoding tumor-associated antigens are currently in development. In the present study, we examined the therapeutic efficacy of vaccination using the mouse alpha-fetoprotein (AFP) gene in mouse hepatocellular carcinoma (HCC) cells. C57L/J or C3H/HeN mice were primed with an injection of naked plasmid DNA expressing mouse AFP followed by a booster of replication-defective adenovirus expressing mouse AFP (plasmid-AFP prime/adenovirus-AFP booster vaccination). The mice were then challenged with high AFP-producing Hepa1-6 cells or low AFP-producing MH134 cells, respectively, and the tumor growth rate was monitored. Plasmid-AFP prime/adenovirus-AFP booster vaccination promoted protective immunity against Hepa1-6 cells, and significantly increased the number of interferon-gamma-producing splenic cells in C57L/J mice. In addition, this vaccination protocol repressed the growth of pre-established Hepa1-6 tumors in C57L/J mice. However, plasmid-AFP prime/adenovirus-AFP booster vaccination did not induce protective immunity against MH134 cells in C3H/HeN mice. These results suggest that vaccination with the AFP gene is a promising strategy to treat HCC, but its outcome may be affected by the level of AFP expression in HCC or by the immunological response of the host.