In animals, effective immune responses against malignancies and against several infectious pathogens, including malaria, are mediated by T cells. Here we show that a heterologous prime-boost vaccination regime of DNA either intramuscularly or epidermally, followed by intradermal recombinant modified vaccinia virus Ankara (MVA), induces high frequencies of interferon (IFN)-γ-secreting, antigen-specific T-cell responses in humans to a pre-erythrocytic malaria antigen, thrombospondin-related adhesion protein (TRAP). These responses are five- to tenfold higher than the T-cell responses induced by the DNA vaccine or recombinant MVA vaccine alone, and produce partial protection manifest as delayed parasitemia after sporozoite challenge with a different strain of Plasmodium falciparum. Such heterologous prime-boost immunization approaches may provide a basis for preventative and therapeutic vaccination in humans.