An HLA allele-specific cytotoxic T lymphocyte response is thought to influence the rate of disease progression in HIV-1-infected individuals. In a prior study of 139 HIV-1-infected homosexual men, we identified HLA class I alleles and observed an association of specific alleles with different relative hazards for progression to AIDS. Seeking an explanation for this association, we searched HIV-1 protein sequences to determine the number of peptides matching motifs defined by combinations of specific amino acids reported to bind 16 class I alleles. Analyzing complete sequences of 12 clade B HIV isolates, we determined the number of allele motifs that were conserved (occurring in all 12 isolates) and nonconserved (occurring in only one isolate), as well as the average number of allele motifs per isolate. We found significant correlations with an allele’s association with disease progression for counts of conserved motifs in gag (R = 0.73; P = 0.002), pol (R = 0.58, P = 0.024), gp120 (R = 0.78, P = 0.00056), and total viral protein sequences (R = 0.67, P = 0.0058) and also for counts of nonconserved motifs in gag (R = 0.62, P = 0.013), pol (R = 0.74, P = 0.0017), gp41 (R = 0.52, P = 0.046), and total viral protein (R = 0.71, P = 0.0033). We also found significant correlations for the average number of motifs per isolate for gag, pol, gp120, and total viral protein. This study provides a plausible functional explanation for the observed association of different HLA alleles with variable rates of disease progression.