Although increasing evidence suggests that CTL are important to fight the development of some cancers, the frequency of detectable tumor-specific T cells is low in cancer patients, and these cells have generally poor functional capacities, compared with virus-specific CD8+ T cells. The generation with a vaccine of potent CTL responses against tumor Ags therefore remains a major challenge. In the present study, ex vivo analyses of Melan-A-specific CD8+ T cells following vaccination with Melan-A peptide and CpG oligodeoxynucleotides revealed the successful induction in the circulation of effective melanoma-specific T cells, ie, with phenotypic and functional characteristics similar to those of CTL specific for immunodominant viral Ags. Nonetheless, the eventual impact on tumor development in vaccinated melanoma donors remained limited. The comprehensive study of vaccinated patient metastasis shows that vaccine-driven tumor-infiltrating lymphocytes, although activated, still differed in functional capacities compared with blood counterparts. This coincided with a significant increase of FoxP3+ regulatory T cell activity within the tumor. The consistent induction of effective tumor-specific CD8+ T cells in the circulation with a vaccine represents a major achievement; however, clinical benefit may not be achieved unless the tumor environment can be altered to enable CD8+ T cell efficacy.