The high prevalence of preexisting immunity to adenovirus serotype 5 (Ad5) in human populations will likely limit the immunogenicity and clinical utility of recombinant Ad5 (rAd5) vector-based vaccines for human immunodeficiency virus type 1 and other pathogens. A potential solution to this problem is to utilize rAd vaccine vectors derived from rare Ad serotypes such as Ad35 and Ad11. We have previously reported that rAd35 vectors were immunogenic in the presence of anti-Ad5 immunity, but the immunogenicity of heterologous rAd prime-boost regimens and the extent that cross-reactive anti-vector immunity may limit this approach have not been fully explored. Here we assess the immunogenicity of heterologous vaccine regimens involving rAd5, rAd35, and novel rAd11 vectors expressing simian immunodeficiency virus Gag in mice both with and without anti-Ad5 immunity. Heterologous rAd prime-boost regimens proved significantly more immunogenic than homologous regimens, as expected. Importantly, all regimens that included rAd5 were markedly suppressed by anti-Ad5 immunity. In contrast, rAd35-rAd11 and rAd11-rAd35 regimens elicited high-frequency immune responses both in the presence and in the absence of anti-Ad5 immunity, although we also detected clear cross-reactive Ad35/Ad11-specific humoral and cellular immune responses. Nevertheless, these data suggest the potential utility of heterologous rAd prime-boost vaccine regimens using vectors derived from rare human Ad serotypes.