A subset of women in the Pumwani Sex Worker Cohort, established in 1985 in Nairobi, Kenya, remains uninfected despite repeated high-risk exposure (HIV-exposed, seronegative [HESN]) through active sex work. This HESN phenotype is associated with several alleles of human leukocyte antigens (HLAs) and specific CD8(+) and CD4(+) T cell responses to HIV-1. The associations of HLA alleles with differential HIV-1 infection are most likely due to their different abilities to present antigen and the different immune responses they induce. The characteristics of epitopes of HLA alleles associated with different outcomes of HIV-1 infection might therefore point to a vital clue for developing an effective vaccine. In this study, we systematically analyzed HIV-1 clade A and D Gag CD8(+) T cell epitopes of two HLA class I alleles associated with different outcomes of HIV-1 infection. Binding affinity and off-rates of the identified epitopes were determined. Gamma interferon (IFN-γ) enzyme-linked immunospot (ELISpot) assays with patient peripheral blood mononuclear cells (PBMCs) validated the epitopes. Epitope-specific CD8(+) T cells were further phenotyped for memory markers with tetramer staining. Our study showed that the protective allele A01:01 recognizes only three Gag epitopes. By contrast, B07:02, the allele associated with susceptibility, binds 30 epitope variants. These two alleles differ most importantly in the spectrum of Gag epitopes they can present and not in affinity, off-rates, the location of the epitopes, or epitope-specific Tem/Tcm frequencies. The binding of more epitopes and strong IFN-gamma ELISpot responses are associated with susceptibility to HIV-1 infection, while more focused antigen recognition of multiple subtypes is protective. Rational vaccine design should take these observations into account.