Sub-Saharan Africa carries the biggest burden of the human immunodeficiency virus type 1 (HIV-1)/AIDS epidemic and is in an urgent need of an effective vaccine. CD8+ T cells are an important component of the host immune response to HIV-1 and may need to be harnessed if a vaccine is to be effective. CD8+ T cells recognize human leukocyte antigen (HLA)-associated viral epitopes and the HLA alleles vary significantly among different ethnic groups. It follows that definition of HIV-1-derived peptides recognized by CD8+ T cells in the geographically relevant regions will critically guide vaccine development. Here, we study fine details of CD8+ T-cell responses elicited in HIV-1/2-uninfected individuals in Nairobi, Kenya, who received a candidate vaccine delivering conserved regions of HIV-1 proteins called HIVconsv. Using 10-day cell lines established by in vitro peptide restimulation of cryopreserved PBMC and stably HLA-transfected 721.221/C1R cell lines, we confirm experimentally many already defined epitopes, for a number of epitopes we define the restricting HLA molecule(s) and describe four novel HLA-epitope pairs. We also identify specific dominance patterns, a promiscuous T-cell epitope and a rescue of suboptimal T-cell epitope induction in vivo by its functional variant, which all together inform vaccine design.