Precise identification of regulatory T cells is crucial in the understanding of their role in human cancers. Here, we analyzed the frequency and phenotype of regulatory T cells (Tregs), in both healthy donors and melanoma patients, based on the expression of the transcription factor FOXP3, which, to date, is the most reliable marker for Tregs, at least in mice. We observed that FOXP3 expression is not confined to human CD25^+/high CD4⁺ T cells, and that these cells are not homogenously FOXP3⁺. The circulating relative levels of FOXP3⁺ CD4⁺ T cells may fluctuate close to 2-fold over a short period of observation and are significantly higher in women than in men. Further, we showed that FOXP3⁺ CD4⁺ T cells are over-represented in peripheral blood of melanoma patients, as compared to healthy donors, and that they are even more enriched in tumor-infiltrated lymph nodes and at tumor sites, but not in normal lymph nodes. Interestingly, in melanoma patients, a significantly higher proportion of functional, antigen-experienced FOXP3⁺ CD4⁺ T was observed at tumor sites, compared to peripheral blood. Together, our data suggest that local accumulation and differentiation of Tregs is, at least in part, tumor-driven, and illustrate a reliable combination of markers for their monitoring in various clinical settings.