The goal of an effective AIDS vaccine is to generate immunity that will prevent human immunodeficiency virus 1 (HIV-1) acquisition. Despite limited progress toward this goal, renewed optimism has followed the recent success of the RV144 vaccine trial in Thailand. However, the lack of complete protection in this trial suggests that breakthroughs, where infection occurs despite adequate vaccination, will be a reality for many vaccine candidates. We previously reported that neutralizing antibodies elicited by DNA prime-recombinant adenovirus serotype 5 (rAd5) boost vaccination with simian immunodeficiency virus strain mac239 (SIVmac239) Gag-Pol and Env provided protection against pathogenic SIVsmE660 acquisition after repeated mucosal challenge. Here, we report that SIV-specific CD8+ T cells elicited by that vaccine lowered both peak and set-point viral loads in macaques that became infected despite vaccination. These SIV-specific CD8+ T cells showed strong virus-inhibitory activity (VIA) and displayed an effector memory (EM) phenotype. VIA correlated with high levels of CD107a mobilization and perforin expression in SIV-specific CD8+ T cells. Remarkably, both the frequency and the number of Gag CM9-specific public clonotypes were strongly correlated with VIA mediated by EM CD8+ T cells. The ability to elicit such virus-specific EM CD8+ T cells might contribute substantially to an efficacious HIV/AIDS vaccine, even after breakthrough infection.