Many people who remain persistently seronegative despite frequent HIV exposure have HIV-specific immune responses. The study of these may provide information about mechanisms of natural protective immunity to HIV-1. We describe the specificity of cytotoxic T lymphocyte responses to HIV in seronegative prostitutes in Nairobi who are apparently resistant to HIV infection. These women have had frequent exposure to a range of African HIV-1 variants, primarily clades A, C, and D, for up to 12 yr without becoming infected. Nearly half of them have CTL directed towards epitopes previously defined for B clade virus, which are largely conserved in the A and D clade sequences. Stronger responses are frequently elicited using the A or D clade version of an epitope to stimulate CTL, suggesting that they were originally primed by exposure to these virus strains. CTL responses have been defined to novel epitopes presented by HLA class I molecules associated with resistance to infection in the cohort, HLA-A*6802 and HLA-B18. Estimates using a modified interferon-gamma Elispot assay indicate a circulating frequency of CTL to individual epitopes of between 1:3,200 and 1:50,000. Thus, HIV-specific immune responses-particularly cross-clade CTL activity- may be responsible for protection against persistent HIV infection in these African women.