HIV-1 Nef and HIV-1-specific cytotoxic T lymphocytes (CTLs) have important and opposing roles in the immunopathogenesis of HIV-1 infection. Nef-mediated down-modulation of HLA class I on infected cells can confer resistance to CTL clearance, but the factors determining the efficiency of this process are unknown. This study examines the impact of Nef on the antiviral activity of several CTL clones recognizing epitopes from early and late HIV-1 proteins, restricted by HLA-A, -B, and -C molecules. CTL-targeting epitopes in early proteins remained susceptible to the effects of Nef, although possibly to a lesser degree than CTL-targeting late protein epitopes, indicating that significant Nef-mediated HLA down-regulation can precede even the presentation of early protein-derived epitopes. However, HLA-C-restricted CTLs were unaffected by Nef, consistent with down-regulation of cell-surface HLA-A and -B but not HLA-C molecules. Thus, CTLs vary dramatically in their susceptibility to Nef interference, suggesting differences in the relative importance of HLA-A- and HLA-B- versus HLA-C-restricted CTLs in vivo. The data thus indicate that HLA-C-restricted CTLs may have an under-appreciated antiviral role in the setting of Nef in vivo and suggest a benefit of promoting HLA-C-restricted CTLs for immunotherapy or vaccine development.