Efficient and persisting immune memory is essential for long-term protection from infectious and malignant diseases. The yellow fever (YF) vaccine is a live attenuated virus that mediates lifelong protection, with recent studies showing that the CD8(+) T cell response is particularly robust. Yet, limited data exist regarding the long-term CD8(+) T cell response, with no studies beyond 5 years after vaccination. We investigated 41 vaccinees, spanning 0.27 to 35 years after vaccination. YF-specific CD8(+) T cells were readily detected in almost all donors (38 of 41), with frequencies decreasing with time. As previously described, effector cells dominated the response early after vaccination. We detected a population of naïve-like YF-specific CD8(+) T cells that was stably maintained for more than 25 years and was capable of self-renewal ex vivo. In-depth analyses of markers and genome-wide mRNA profiling showed that naïve-like YF-specific CD8(+) T cells in vaccinees (i) were distinct from genuine naïve cells in unvaccinated donors, (ii) resembled the recently described stem cell-like memory subset (Tscm), and (iii) among all differentiated subsets, had profiles closest to naïve cells. Our findings reveal that CD8(+) Tscm are efficiently induced by a vaccine in humans, persist for decades, and preserve a naïveness-like profile. These data support YF vaccination as an optimal mechanistic model for the study of long-lasting memory CD8(+) T cells in humans.