We have previously shown that vaccination of HLA-A2 metastatic melanoma patients with the analogue Melan-A(26-35(A27L)) peptide emulsified in a mineral oil induces ex vivo detectable specific CD8 T cells. These are further enhanced when a TLR9 agonist is codelivered in the same vaccine formulation. Interestingly, the same peptide can be efficiently recognized by HLA-DQ6-restricted CD4 T cells. We used HLA-DQ6 multimers to assess the specific CD4 T-cell response in both healthy individuals and melanoma patients. We report that the majority of melanoma patients carry high frequencies of naturally circulating HLA-DQ6-restricted Melan-A-specific CD4 T cells, a high proportion of which express FOXP3 and proliferate poorly in response to the cognate peptide. Upon vaccination, the relative frequency of multimer+ CD4 T cells did not change significantly. In contrast, we found a marked shift to FOXP3-negative CD4 T cells, accompanied by robust CD4 T-cell proliferation upon in vitro stimulation with cognate peptide. A concomitant reduction in TCR diversity was also observed. This is the first report on direct ex vivo identification of antigen-specific FOXP3+ T cells by multimer labeling in cancer patients and on the direct assessment of the impact of peptide vaccination on immunoregulatory T cells.