The development of an effective malaria vaccine is a high global health priority. Vaccine vectors based on adenovirus type 5 are capable of generating robust and protective T cell and antibody responses in animal models and are currently being evaluated in clinical trials for HIV and malaria. They appear to be more effective in terms of inducing antigen-specific immune responses as compared with non-Ad5 serotype vectors. However, the high prevalence of neutralizing antibodies to Ad5 in the human population, particularly in the developing world, has the potential to limit the effectiveness of Ad5-based vaccines. We have generated novel Ad5-based vectors that precisely replace the hexon hypervariable regions with those derived from Ad43, a subgroup D serotype with low prevalence of neutralizing antibody in humans. We have demonstrated that these hexon-modified adenovectors are not neutralized efficiently by Ad5 neutralizing antibodies in vitro using sera from mice, rabbits and human volunteers. We have also generated hexon-modified adenovectors that express a rodent malaria parasite antigen, PyCSP, and demonstrated that they are as immunogenic as an unmodified vector. Furthermore, in contrast to the unmodified vector, the hexon-modified adenovectors induced robust T cell responses in mice with high levels of Ad5 neutralizing antibody. We also show that the hexon-modified vector can be combined with unmodified Ad5 vector in prime-boost regimens to induce protective responses in mice. Our data establish that these hexon-modified vectors are highly immunogenic even in the presence of pre-existing anti-adenovirus antibodies. These hexon-modified adenovectors may have advantages in sub-Saharan Africa where there is a high prevalence of Ad5 neutralizing antibody in the population.