The frequency and function of regulatory T cells (Tregs) were studied in stage II-III melanoma patients who were enrolled in a phase II randomized trial of vaccination with HLA-A*0201-modified tumor peptides versus observation. The vaccinated patients received low-dose cyclophosphamide (CTX) and low-dose interleukin-2 (IL-2). Tregs were analyzed in the lymph nodes (LNs) of stage III patients who were undergoing complete lymph node dissection and in peripheral blood mononuclear cells (PBMCs) collected before vaccination and at different time points during the vaccination period. The LNs of the vaccinated patients, which were surgically removed after two rounds of vaccination and one dose of CTX, displayed a low frequency of Tregs and a less immunosuppressive environment compared with those of the untreated patients. The accurate time-course analysis of the PBMCs of patients enrolled in the vaccination arm indicated a limited and transient modulation in the frequencies of Tregs in PBMCs collected after low-dose CTX administration and a strong Treg boost in those PBMCs collected after low-dose IL-2 administration. However, a fraction of the IL-2-boosted Tregs was functionally modulated to a Th-1-like phenotype in the vaccinated patients. Moreover, low-dose IL-2 promoted the concomitant expansion of conventional activated CD4(+) T cells. Despite the amplification of Tregs, IL-2 administration maintained or further increased the number of antigen-specific CD8(+) T cells that were induced by vaccination as demonstrated by the ex vivo human leukocyte antigen-multimer staining and IFN-γ ELISpot assays. Our study suggests that the use of CTX as a Treg modulator should be revised in terms of the administration schedule and of patients who may benefit from this drug treatment. Despite the Treg expansion that was observed in this study, low-dose IL-2 is not detrimental to the functional activities of vaccine-primed CD8(+) T cell effectors when used in the inflammatory environment of vaccination.