Human immunodeficiency virus (HIV) induces strong responses from human histocompatibility leukocyte antigen (HLA) class I-restricted cytotoxic T lymphocytes (CTL). In a previous report we identified an immunodominant region (amino acids 73-144) in the NEF protein that was recognized by CD8+ class I-restricted CTL of most asymptomatic individuals. Analysis of the 73-144 region by peptide sensitization, experiments using overlapping peptides corresponding to the LAI isolate identified the peptide sequences located between residues 73 and 82 or 84 and 92 and the peptide sequence between residues 134 and 144 as cognate peptides for HLA-A11- and HLA-B18-restricted epitopes, respectively. This report describes the variable demonstrable reactivities of CTL obtained from HLA-A11 or HLA-B18 seropositive, asymptomatic patients who all had a response to the virus NEF protein, but who did not always recognize appropriate cognate peptides. The high mutation rate of HIV probably facilitates the selection of mutants that can avoid the cellular immune response. We therefore analyzed the variability of these epitopes restricted by HLA-A11 and HLA-B18. We sequenced several viral isolates from HLA-A11 and HLA-B18 donors who recognized certain HLA-peptide complexes and from those who did not. A CTL sensitization assay was used to show that some mutations led to a great reduction in CTL activity in vitro. This might be due to failure of the mutated epitope to bind major histocompatibility complex class I molecule. A simple assay was used to detect peptides that promoted the assembly of class I molecules. Some of these mutations at major anchor positions prevented HLA-A11/peptide binding, and consequently impaired recognition of the HLA-peptide complex by the T cell receptor.