A recombinant adenovirus serotype 5 (rAd5) vector-based vaccine for HIV-1 has recently failed in a phase 2b efficacy study in humans. Consistent with these results, preclinical studies have demonstrated that rAd5 vectors expressing simian immunodeficiency virus (SIV) Gag failed to reduce peak or setpoint viral loads after SIV challenge of rhesus monkeys (Macaca mulatta) that lacked the protective MHC class I allele Mamu-A*01 (ref. 3). Here we show that an improved T-cell-based vaccine regimen using two serologically distinct adenovirus vectors afforded substantially improved protective efficacy in this challenge model. In particular, a heterologous rAd26 prime/rAd5 boost vaccine regimen expressing SIV Gag elicited cellular immune responses with augmented magnitude, breadth and polyfunctionality as compared with the homologous rAd5 regimen. After SIV(MAC251) challenge, monkeys vaccinated with the rAd26/rAd5 regimen showed a 1.4 log reduction of peak and a 2.4 log reduction of setpoint viral loads as well as decreased AIDS-related mortality as compared with control animals. These data demonstrate that durable partial immune control of a pathogenic SIV challenge for more than 500 days can be achieved by a T-cell-based vaccine in Mamu-A*01-negative rhesus monkeys in the absence of a homologous Env antigen. These findings have important implications for the development of next-generation T-cell-based vaccine candidates for HIV-1.