Adenovirus serotype 35 (Ad35) is a promising vaccine platform for human immunodeficiency virus (HIV) infection and emerging infectious diseases as it is uncommon in humans worldwide and is distinct from Ad5, the major vaccine serotype for which many individuals have pre-existing immunity. The immunogenicity of a first-generation, replication-competent Ad35-based vaccine was tested in the simian immunodeficiency virus (SIV) rhesus macaque model by evaluating its capacity to boost immunity generated by Ad5-based vectors. A series of four immunizations with replication-defective Ad5 vectors expressing SIVmac239 gag induced high-frequency responses mediated by both CD8+ and CD4+ T cells directed against several epitopes. Ad5-specific neutralizing antibody responses that did not neutralize Ad35 were rapidly induced but waned over time. Subsequent immunization with Ad5-based vectors was minimally effective, whereas immunization with Ad35-based vectors generated a strong increase in the frequency of Gag-specific T cells with specificities that were unchanged. While this boosting response was relatively transient, challenge with the distinct pathogenic isolate SIV/DeltaB670 generated robust and selective recall responses to Gag with similar specificities as induced by vaccination that were elevated for 25 weeks relative to controls. Vaccination had measurable albeit minor effects on virus load. Unexpectedly, regional hypervariability within the Gag sequence of SIV/DeltaB670 was associated with mutation of the conserved CD8+ T-cell epitope CM9 without concurrent flanking mutations and in the absence of immune pressure. These findings support the further development of Ad35 as a vaccine vector, and promote vaccine regimens that utilize serial administration of heterologous adenoviruses.