Live vectors expressing foreign antigens have been used to induce immunity against several pathogens. However, for the virulent rodent malaria parasite Plasmodium yoelii, the use of recombinant vaccinia virus, pseudorabies virus, or Salmonella, expressing the circumsporozoite protein of this parasite, failed to induce protection. We generated a recombinant influenza virus expressing an epitope from the circumsporozoite protein of P. yoelii known to be recognized by CD8+ T cells and demonstrated that this vector induced class I major histocompatibility complex-restricted cytotoxic T cells against this foreign epitope. Immunization of mice with this recombinant influenza virus, followed by a recombinant vaccinia virus expressing the entire circumsporozoite protein, induced protective immunity against sporozoite-induced malaria. The sequence of immunization appears to be crucial, since a primer injection with recombinant vaccinia virus, followed by a booster injection with recombinant influenza virus, failed to induce protection. The protection induced by immunization with these recombinant viruses is mostly mediated by CD8+ T cells, as treatment of mice with anti-CD8 monoclonal antibody abolishes the anti-malarial immunity. The use of different live vectors for primer and booster injections has a synergistic effect on the immune response and might represent an effective general strategy for eliciting protective immune responses to key antigens of microbial pathogens.