A crucial requirement in the rational design of a prophylactic vaccine against the human immunodeficiency virus (HIV) is to establish whether or not protective immunity can occur following natural infection. The immune response to HIV infection is characterized by very vigorous HIV-specific cytotoxic T-lymphocyte (CTL) activity. We have identified four HIV-1 and HIV-2 cross-reactive peptide epitopes, presented to CTL from HIV-infected Gambians by HLA-B35 (the most common Gambian class I HLA molecule). These peptides were used to elicit HIV-specific CTLs from three out of six repeatedly exposed but HIV-seronegative female prostitutes with HLA-B35. These women remain seronegative with no evidence of HIV infection by polymerase chain reaction or viral culture. Their CTL activity may represent protective immunity against HIV infection.