The high prevalence of preexisting immunity to adenovirus serotype 5 (Ad5) in human populations has led to the development of recombinant adenovirus (rAd) vectors derived from rare Ad serotypes as vaccine candidates for human immunodeficiency virus type 1 and other pathogens. Vaccine vectors have been constructed from Ad subgroup B, including rAd11 and rAd35, as well as from Ad subgroup D, including rAd49. However, the optimal combination of vectors for heterologous rAd prime-boost vaccine regimens and the extent of cross-reactive vector-specific neutralizing antibodies (NAbs) remain poorly defined. We have shown previously that the closely related vectors rAd11 and rAd35 elicited low levels of cross-reactive NAbs. Here we show that these cross-reactive NAbs correlated with substantial sequence homology in the hexon hypervariable regions (HVRs) and suppressed the immunogenicity of heterologous rAd prime-boost regimens. In contrast, vectors with lower hexon HVR homology, such as rAd35 and rAd49, did not elicit detectable cross-reactive vector-specific NAbs. Consistent with these findings, rAd35-rAd49 vaccine regimens proved more immunogenic than both rAd35-rAd5 and rAd35-rAd11 regimens in mice with anti-Ad5 immunity. These data suggest that optimal heterologous rAd prime-boost regimens should include two vectors that are both rare in human populations to circumvent preexisting antivector immunity as well as sufficiently immunologically distinct to avoid cross-reactive antivector immunity.