The etiological role of human papillomaviruses (HPV) in cervical and other cancers suggests that therapeutic vaccines directed against requisite viral antigens may eradicate tumors or their precursors. A Venezuelan equine encephalitis (VEE) alphavirus vector delivering the HPV16 E7 RNA was evaluated for antitumor efficacy using a murine E7+ tumor model. Vaccination with VEE replicon particles expressing E7 (E7-VRP) induced class I-restricted CD8+ T-cell responses as determined by IFN-gamma enzyme-linked immunospot (ELISPOT), tetramer, and cytotoxicity assays. E7-VRP vaccination prevented tumor development in all of the mice and effectively eliminated 7-day established tumors in 67% of tumor-bearing mice. The induction of protective T-cell responses was dependent on CD8+, but not CD4+ T cells. Long-lasting T-cell memory responses developed in E7-VRP-vaccinated mice as determined by complete protection from tumor challenge 3 months after the final vaccination. These promising results highlight the potent CD8+ T-cell-mediated antitumor effects elicited by VEE replicon-based vectors and support their further development toward clinical testing against cervical intraepithelial neoplasia or carcinoma.