Although current polyvalent vaccines can prevent development of cervical cancer, they cannot be used to treat patients who already have the disease. Adenovirus expressing calreticulin-E7 (Ad-CRT-E7) has shown promising results in the cervical cancer murine model. We also demonstrated that immunization with Lactococcus lactis encoding HPV-16 E7 (Ll-E7) anchored to its surface induces significant HPV-16 E7-specific immune response. Here, we assessed the combination of both approaches in the treatment of a cervical cancer animal model. Intranasal preimmunization of Ll-E7, followed by a single Ad-CRT/E7 application, induced ∼80% of tumor suppression in comparison with controls. Mice treated with a combination of Ll-E7 and Ad-CRT/E7 resulted in a 70% survival rate 300 days post-treatment, whereas 100% of the mice in the control groups died by 50 days. Significant CD8+ cytotoxic T-lymphocytes infiltration was detected in the tumors of mice treated with Ll-E7+Ad-CRT/E7. Tumors with regression showed a greater number of positive cells for in situ TUNEL staining than controls. Our results suggest that preimmunization with Ll-E7 enhances the Ad-CRT/E7-mediated antitumor effect. This treatment provides an enormous advantage over repeated applications of Ad-CRT/E7 by maintaining the effectiveness of the three-dose application of Ad-CRT/E7, but avoiding the high systemic toxicities associated with such repeat treatments.