Induction of cytotoxic CD8 T-cell responses is enhanced by the exclusive presentation of antigen through dendritic cells, and by innate stimuli, such as toll-like receptor ligands. On the basis of these 2 principles, we designed a vaccine against melanoma. Specifically, we linked the melanoma-specific Melan-A/Mart-1 peptide to virus-like nanoparticles loaded with A-type CpG, a ligand for toll-like receptor 9. Melan-A/Mart-1 peptide was cross-presented, as shown in vitro with human dendritic cells and in HLA-A2 transgenic mice. A phase I/II study in stage II-IV melanoma patients showed that the vaccine was well tolerated, and that 14/22 patients generated ex vivo detectable T-cell responses, with in part multifunctional T cells capable to degranulate and produce IFN-γ, TNF-α, and IL-2. No significant influence of the route of immunization (subcutaneous versus intradermal) nor dosing regimen (weekly versus daily clusters) could be observed. It is interesting to note that, relatively large fractions of responding specific T cells exhibited a central memory phenotype, more than what is achieved by other nonlive vaccines. We conclude that vaccination with CpG loaded virus-like nanoparticles is associated with a human CD8 T-cell response with properties of a potential long-term immune protection from the disease.