Adenovirus 5 (Ad5) vectors show promise as human immunodeficiency virus vaccine candidates. Indian rhesus macaques vaccinated with Ad5-gag controlled simian-human immunodeficiency virus SHIV89.6P viral replication in the absence of Env immunogens that might elicit humoral immunity. Here we immunized 15 macaques using either a homologous Ad5-gag/Ad5-gag (Ad5/Ad5) or a heterologous DNA-gag/Ad5-gag (DNA/Ad5) prime-boost regimen and challenged them with a high dose of simian immunodeficiency virus SIVmac239. Macaques vaccinated with the DNA/Ad5 regimen experienced a brief viral load nadir of less than 10,000 viral copies per ml blood plasma that was not seen in Mamu-A*01-negative DNA/Ad5 vaccinees, Mamu-A*01-positive Ad5/Ad5 vaccinees, or vaccine-naive controls. Interestingly, most of these animals were not durably protected from disease progression when challenged with SIVmac239. To investigate the reasons underlying this short-lived vaccine effect, we investigated breadth of the T-cell response, immunogenetic background, and viral escape from CD8⁺ lymphocytes that recognize immunodominant T-cell epitopes. We show that these animals do not mount unusually broad cellular immune response, nor do they express unusual major histocompatibility complex class I alleles. Viral recrudescence occurred in four of the five Mamu-A*01-positive vaccinated macaques. However, only a single animal in this group demonstrated viral escape in the immunodominant Gag_181-189CM9 response. These results suggest that viral “breakthrough” in vaccinated animals and viral escape are not inextricably linked and underscore the need for additional research into the mechanisms of vaccine failure.