Replication-defective adenovirus type 5 (Ad5) vector-based vaccines are widely known to induce strong immunity against immunodeficiency viruses. To exploit this immunogenicity while overcoming the potential problem of preexisting immunity against human adenoviruses type 5, we developed a recombinant chimeric adenovirus type 5 with type 35 fiber vector (rAd5/35). We initially produced a simian immunodeficiency virus (SIV) gag DNA plasmid (rDNA-Gag), a human immunodeficiency virus type 1 (HIV-1) 89.6 env DNA plasmid (rDNA-Env) and a recombinant Ad5/35 vector encoding the SIV gag and HIV env gene (rAd5/35-Gag and rAd5/35-Env). Prime-boost vaccination with rDNA-Gag and -Env followed by high doses of rAd5/35-Gag and -Env elicited higher levels of cellular immune responses than did rDNAs or rAd5/35s alone. When challenged with a pathogenic simian human immunodeficiency virus (SHIV), animals receiving a prime-boost regimen or rAd5/35s alone maintained a higher number of CD4(+) T cells and remarkably suppressed plasma viral RNA loads. These findings suggest the clinical promise of an rAd5/35 vector-based vaccine.