An ideal malaria vaccine should target several stages of the parasite life cycle and induce antiparasite and antidisease immunity. We have reported a Plasmodium yoelii chimeric multistage recombinant protein (P. yoelii linear peptide chimera/recombinant modular chimera), engineered to express several autologous T cell epitopes and sequences derived from the circumsporozoite protein and the merozoite surface protein 1. This chimeric protein elicits protective immunity, mediated by CD4+ T cells and neutralizing Abs. However, experimental evidence, from pre-erythrocytic vaccine candidates and irradiated sporozoites, has shown that CD8+ T cells play a significant role in protection. Recombinant viral vectors have been used as a vaccine platform to elicit effective CD8+ T cell responses. The human adenovirus (Ad) serotype 5 has been tested in malaria vaccine clinical trials with excellent safety profile. Nevertheless, a major concern for the use of Ad5 is the high prevalence of anti-vector neutralizing Abs in humans, hampering its immunogenicity. To minimize the impact of anti-vector pre-existing immunity, we developed a chimeric Ad5/3 vector in which the knob region of Ad5 was replaced with that of Ad3, conferring partial resistance to anti-Ad5 neutralizing Abs. Furthermore, we implemented heterologous Ad/protein immunization regimens that include a single immunization with recombinant Ad vectors. Our data show that immunization with the recombinant Ad5/3 vector induces protective efficacy indistinguishable from that elicited by Ad5. Our study also demonstrates that the dose of the Ad vectors has an impact on the memory profile and protective efficacy. The results support further studies with Ad5/3 for malaria vaccine development. The Journal of Immunology, 2016, 197: 2748-2761.