Cervical cancer continues to impose a heavy burden worldwide, and human papilloma virus (HPV) infection, especially persistent infection with type 16 (HPV-16), is known to be the primary etiological factor. Therapeutic vaccines are urgently needed because prophylactic vaccines are ineffective at clearing pre-existing HPV infection. Here, two recombinant Listeria strains (LMΔ-E6E7 & LIΔ-E6E7) with deletions of the actA and plcB genes, expressing the shuffled HPV-16 E6E7 protein were constructed. The strains were delivered into the spleen and liver by intravenous inoculation, induced antigen-specific cellular immunity and were eliminated completely from the internal organs several days later. Intravenously treating with single strain for three times, or with both strains alternately for three times significantly reduced the tumor size and prolonged the survival time of model mice. Combination immunotherapy with two strains seemed more effective than immunotherapy with single strain in that it enhanced the survival of the mice, and the LMΔ-E6E7-prime-LIΔ-E6E7-boost strategy showed significant stronger efficacy than single treatment with the LIΔ-E6E7 strain. The antitumor effect of this treatment might due to its ability to increase the proportion of CD8+ T cells and reduce the proportion of T regulatory cells (Tregs) in the intratumoral milieu. This is the first report regarding Listeria ivanovii-based therapeutic vaccine candidate against cervical cancer. Most importantly we are the first to confirm that combination therapy with two different recombinant Listeria strains has a more satisfactory antitumor effect than administration of a single strain. Thus, we propose a novel prime-boost treatment strategy.