HIV-1–specific cytotoxic T-lymphocyte (CTL) responses have been detected at a low frequency in many HIV-1–exposed, persistently seronegative (HEPS) subjects. However, it is unclear how CTLs could protect against HIV acquisition in HEPS subjects, when high levels of circulating CTL fail to prevent disease progression in most seropositive subjects. To address this issue we studied CD8⁺ lymphocyte responses to a panel of HIV-1 CTL epitopes in 91 HEPS and 87 HIV-1–infected Nairobi sex workers. HIV-specific responses in seropositive women focused strongly on epitopes rarely or never recognized in HEPS subjects, who targeted epitopes that were subdominant or unrecognized in infected women. These differences in epitope specificity were restricted by only those HLA class I alleles that are associated with a reduced risk of HIV-1 infection in this cohort. Late seroconversion in HEPS donors was associated with a switch in epitope specificity and/or immunodominance to those epitopes preferentially recognized by HIV-1–infected women. The likelihood of detecting HIV-1–specific responses in HEPS women increased with the duration of viral exposure, suggesting that HIV-1–specific CD8⁺ responses are acquired over time. The association between differential recognition of distinct CTL epitopes and protection from HIV-1 infection may have significant implications for vaccine design.