A rare subset of human immunodeficiency virus (HIV)-infected individuals maintains undetectable HIV RNA levels without therapy (“elite controllers”). To clarify the role of T-cell responses in mediating virus control, we compared HLA class I polymorphisms and HIV-specific T-cell responses among a large cohort of elite controllers (HIV-RNA < 75 copies/ml), “viremic” controllers (low-level viremia without therapy), “noncontrollers” (high-level viremia), and “antiretroviral therapy suppressed” individuals (undetectable HIV-RNA levels on antiretroviral therapy). The proportion of CD4⁺ and CD8⁺ T cells that produce gamma interferon (IFN-γ) and interleukin-2 (IL-2) in response to Gag and Pol peptides was highest in the elite and viremic controllers (P < 0.0001). Forty percent of the elite controllers were HLA-B*57 compared to twenty-three percent of viremic controllers and nine percent of noncontrollers (P < 0.001). Other HLA class I alleles more common in elite controllers included HLA-B*13, HLA-B*58, and HLA-B*81 (P < 0.05 for each). Within elite and viremic controller groups, those with protective class I alleles had higher frequencies of Gag-specific CD8⁺ T cells than those without these alleles (P = 0.01). Noncontrollers, with or without protective alleles, had low-level CD8⁺ responses. Thus, certain HLA class I alleles are enriched in HIV controllers and are associated with strong Gag-specific CD8⁺IFN-γ⁺IL-2⁺ T cells. However, the absence of evidence of T cell-mediated control in many controllers suggests the presence of alternative mechanisms for viral control in these individuals. Defining mechanisms for virus control in “non-T-cell controllers” might lead to insights into preventing HIV transmission or preventing virus replication.