One of the major hurdles facing cancer immunotherapy is that cancers may downregulate expression of MHC class I molecules. The development of a suitable tumor model with downregulated MHC class I expression is critical for designing vaccines and immunotherapeutic strategies to control such tumors. We developed an E7-expressing murine tumor model with downregulated MHC class I expression, TC-1 P3 (A15). Using this model, we tested DNA and vaccinia vaccines for their ability to control tumors with downregulated MHC class I expression. We found that vaccination with DNA encoding E7 linked to Mycobacterial heat shock protein 70 (HSP70) generated a significant antitumor effect against TC-1 P3 (A15), while vaccination with E7/HSP70 vaccinia did not generate an appreciable antitumor effect. Lymphocyte depletion experiments revealed that both CD8+ T cells and NK cells were essential for the antitumor effect generated by E7/HSP70 DNA against TC-1 P3 (A15). Furthermore, tumor protection experiments using IFN-gamma knockout mice revealed that IFN-gamma was essential for the antitumor effect generated by E7/HSP70 DNA against TC-1 P3 (A15). Our results demonstrate that vaccination with E7/HSP70 DNA results in a significant antitumor effect against a neoplasm with downregulated MHC class I expression and the importance of CD8+ T cells, NK cells, and IFN-gamma in generating this antitumor effect.