CD8+ T cells are a key focus of vaccine development efforts for HIV. However, there is no clear consensus as to which of the nine HIV proteins should be used for vaccination. The early proteins Tat, Rev, and Nef may be better CD8+ T cell targets than the late-expressed structural proteins Gag, Pol, and Env. In this study, we show that Gag-specific CD8+ T cells recognize infected CD4+ T lymphocytes as early as 2 h postinfection, before proviral DNA integration, viral protein synthesis, and Nef-mediated MHC class I down-regulation. Additionally, the number of Gag epitopes recognized by CD8+ T cells was significantly associated with lower viremia (p= 0.0017) in SIV-infected rhesus macaques. These results suggest that HIV vaccines should focus CD8+ T cell responses on Gag.