The possession of some HLA class I molecules is associated with delayed progression to AIDS. The mechanism behind this beneficial effect is unclear. We tested the idea that cytotoxic T-cell responses restricted by advantageous HLA class I molecules impose stronger selection pressures than those restricted by other HLA class I alleles. As a measure of the selection pressure imposed by HLA class I alleles, we determined the extent of HLA class I-associated epitope variation in a cohort of European human immunodeficiency virus (HIV)-positive individuals (n = 84). We validated our findings in a second, distinct cohort of African patients (n = 516). We found that key HIV epitopes restricted by advantageous HLA molecules (B27, B57, and B51 in European patients and B5703, B5801, and B8101 in African patients) were more frequently mutated in individuals bearing the restricting HLA than in those who lacked the restricting HLA class I molecule. HLA alleles associated with clinical benefit restricted certain epitopes for which the consensus peptides were frequently recognized by the immune response despite the circulating virus's being highly polymorphic. We found a significant inverse correlation between the HLA-associated hazard of disease progression and the mean HLA-associated prevalence of mutations within epitopes (P = 0.028; R2 = 0.34). We conclude that beneficial HLA class I alleles impose strong selection at key epitopes. This is revealed by the frequent association between effective T-cell responses and circulating viral escape mutants and the rarity of these variants in patients who lack these favorable HLA class I molecules, suggesting a significant pressure to revert.