The induction of potent CD8+ T cell responses by vaccines to fight microbes or tumors remains a major challenge, as many candidates for human vaccines have proved to be poorly immunogenic. Deoxycytidyl-deoxyguanosin oligodeoxynucleotides (CpG ODNs) trigger Toll-like receptor 9, resulting in dendritic cell maturation that can enhance immunogenicity of peptide-based vaccines in mice. We tested whether a synthetic ODN, CpG 7909, could improve human tumor antigen-specific CD8+ T cell responses. Eight HLA-A2+ melanoma patients received 4 monthly vaccinations of low-dose CpG 7909 mixed with melanoma antigen A (Melan-A; identical to MART-1) analog peptide and incomplete Freund's adjuvant. All patients exhibited rapid and strong antigen-specific T cell responses: the frequency of Melan-A-specific T cells reached over 3% of circulating CD8+ T cells. This was one order of magnitude higher than the frequency seen in 8 control patients treated similarly but without CpG and 1-3 orders of magnitude higher than that seen in previous studies with synthetic vaccines. The enhanced T cell populations consisted primarily of effector memory cells, which in part secreted IFN- and expressed granzyme B and perforin ex vivo. In vitro, T cell clones recognized and killed melanoma cells in an antigen-specific manner. Thus, CpG 7909 is an efficient vaccine adjuvant that promotes strong antigen-specific CD8+ T cell responses in humans.