The safety, immunogenicity, and efficacy of DNA and modified vaccinia virus Ankara (MVA) prime-boost regimes were assessed by using either thrombospondin-related adhesion protein (TRAP) with a multiple-epitope string ME (ME-TRAP) or the circumsporozoite protein (CS) of Plasmodium falciparum. Sixteen healthy subjects who never had malaria (malaria-naive subjects) received two priming vaccinations with DNA, followed by one boosting immunization with MVA, with either ME-TRAP or CS as the antigen. Immunogenicity was assessed by ex vivo gamma interferon (IFN-gamma) enzyme-linked immunospot assay (ELISPOT) and antibody assay. Two weeks after the final vaccination, the subjects underwent P. falciparum sporozoite challenge, with six unvaccinated controls. The vaccines were well tolerated and immunogenic, with the DDM-ME TRAP regimen producing stronger ex vivo IFN-gamma ELISPOT responses than DDM-CS. One of eight subjects receiving the DDM-ME TRAP regimen was completely protected against malaria challenge, with this group as a whole showing significant delay to parasitemia compared to controls (P = 0.045). The peak ex vivo IFN-gamma ELISPOT response in this group correlated strongly with the number of days to parasitemia (P = 0.033). No protection was observed in the DDM-CS group. Prime-boost vaccination with DNA and MVA encoding ME-TRAP but not CS resulted in partial protection against P. falciparum sporozoite challenge in the present study.