Using a mouse neuroblastoma cell line, we have demonstrated that vaccination of tumor-free mice with a cell-based vaccine leads to productive immunity and resistance to tumor challenge, while vaccination of tumor-bearing mice does not. The T cell immunity induced by this vaccine, as measured by in vitro assays, is amplified by the depletion of Treg. Our goal is to understand this barrier to the development of protective cellular immunity. mRNA microarray analyses of CD8(+) T cells from naïve or tumor-bearing mice undergoing vaccination were carried out with or without administering anti-CD25 antibody. Gene-expression pathway analysis revealed the presence of CD8(+) T cells expressing stem cell-associated genes early after induction of productive anti-tumor immunity in tumor-free mice, prior to any phenotypic changes, but not in tumor-bearing mice. These data demonstrate that early after the induction of productive immune response, cells within the CD8(+) T cell compartment adopt a stem cell-related genetic phenotype that correlates with increased anti-tumor function.