A crucial requirement in the rational design of a prophylactic vaccine against the hu-uman 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.