Human immunodeficiency virus (HIV)-specific cytotoxic T lymphocytes (CTL) play an important role in HIV infection. Given the viral genetic diversity, the selection of suitable antigens and epitope variants will be important in the design of an effective vaccine. We have previously shown that combinatorial libraries are useful tools to identify epitope mimics as well as potentially cross-reactive natural sequences in protein databases. We have applied this approach to the HIV Gag p17-derived epitope SL9 (SLYNTVATL) to identify broadly recognized SL9 mimics and to assess the cross-recognition of naturally occurring SL9 variants. Nine nonapeptides were identified that were up to one order of magnitude more effective than SL9 in stimulating CTL responses in PBMC from HIV-infected subjects. Using transgenic mice, we demonstrate that a number of these epitope mimics were able to generate de novo T cell responses that cross-reacted with the original SL9 sequence. Particularly, mimics with changes at the relatively conserved F-pocket anchor residue were frequently cross-recognized. This approach may lead to vaccine candidates with higher in vivo immunogenicity and increased potential for cross-recognition of naturally occurring SL9 variants.