The importance of CD8⁺ T-cell responses in the control of human immunodeficiency virus type 1 (HIV-1) infection has been demonstrated, yet few studies have been able to correlate these responses with markers of HIV-1 disease progression. This study measured cell-mediated immune responses using peripheral blood mononuclear cells (PBMC) obtained from 27 patients with chronic HIV-1 infection, the majority of whom were off antiretroviral therapy. The ELISPOT assay was used to detect gamma interferon-secreting PBMC after stimulation with overlapping HIV-1 peptides spanning the Gag, Pol, Env, and Nef proteins in addition to the baculovirus-derived p24 and gp160 proteins. All volunteers had responses to at least one HIV-1-specific peptide. All but one of the subjects (96%) responded to the Gag peptide pool, and 86% responded to the Pol and/or Nef peptide pools. The magnitude and the breadth of T-cell responses directed to either the Gag or p24 peptide pools correlated inversely with viral load in plasma (r = −0.60, P < 0.001 and r = −0.52, P < 0.005, respectively) and directly with absolute CD4⁺ T-cell counts (r = 0.54, P < 0.01 and r = 0.39, P < 0.05, respectively) using the Spearman rank correlation test. Responses to the Pol and integrase peptide pools also correlated with absolute CD4⁺ T-cell counts (r = 0.45, P < 0.05 and r = 0.49, P < 0.01, respectively). No correlation with markers of disease progression was seen with specific T-cell responses directed toward the Env or Nef peptides. These data serve as strong evidence that major histocompatibility complex class I presentation of Gag peptides is an essential feature for any HIV-1 vaccine designed to elicit optimal CD8⁺ T-cell responses.