The search for an efficacious vaccine against malaria is ongoing, and it is now widely believed that to confer protection a vaccine must induce very strong cellular and humoral immunity concurrently. We studied the immune response in mice immunized with the recombinant viral vaccines fowlpox strain FP9 and modified virus Ankara (MVA), a protein vaccine (CV-1866), or a combination of the two; all vaccines express parts of the same preerythrocytic malaria antigen, the Plasmodium berghei circumsporozoite protein (CSP). Mice were then challenged with P. berghei sporozoites to determine the protective efficacies of different vaccine regimens. Two immunizations with the protein vaccine CV-1866, based on the hepatitis B core antigen particle, induced strong humoral immunity to the repeat region of CSP that was weakly protective against sporozoite challenge. Prime-boost with the viral vector vaccines, FP9 followed by MVA, induced strong T-cell immunity to the CD8+ epitope Pb9 and partially protected animals from challenge. Physically mixing CV-1866 with FP9 or MVA and then immunizing with the resultant combinations in a prime-boost regimen induced both cellular and humoral immunity and afforded substantially higher levels of protection (combination, 90%) than either vaccine alone (CV-1866, 12%; FP9/MVA, 37%). For diseases such as malaria in which different potent immune responses are required to protect against different stages, using combinations of partially effective vaccines may offer a more rapid route to achieving deployable levels of efficacy than individual vaccine strategies.