CD8 T cells play a key role in mediating protective immunity against selected pathogens after vaccination. Understanding the mechanism of this protection is dependent upon definition of the heterogeneity and complexity of cellular immune responses generated by different vaccines. Here, we identify previously unrecognized subsets of CD8 T cells based upon analysis of gene-expression patterns within single cells and show that they are differentially induced by different vaccines. Three prime-boost vector combinations encoding HIV Env stimulated antigen-specific CD8 T-cell populations of similar magnitude, phenotype, and functionality. Remarkably, however, analysis of single-cell gene-expression profiles enabled discrimination of a majority of central memory (CM) and effector memory (EM) CD8 T cells elicited by the three vaccines. Subsets of T cells could be defined based on their expression of Eomes, Cxcr3, and Ccr7, or Klrk1, Klrg1, and Ccr5 in CM and EM cells, respectively. Of CM cells elicited by DNA prime-recombinant adenoviral (rAd) boost vectors, 67% were Eomes(-) Ccr7(+) Cxcr3(-), in contrast to only 7% and 2% stimulated by rAd5-rAd5 or rAd-LCMV, respectively. Of EM cells elicited by DNA-rAd, 74% were Klrk1(-) Klrg1(-)Ccr5(-) compared with only 26% and 20% for rAd5-rAd5 or rAd5-LCMV. Definition by single-cell gene profiling of specific CM and EM CD8 T-cell subsets that are differentially induced by different gene-based vaccines will facilitate the design and evaluation of vaccines, as well as enable our understanding of mechanisms of protective immunity.