Using fluorescent HLA-A*0201 tetramers containing the immunodominant Melan-A/MART-1 (Melan-A) tumor-associated antigen (Ag), we previously observed that metastatic lymph nodes of melanoma patients contain high numbers of Ag-experienced Melan-A-specific cytolytic T lymphocytes (CTLs). In this paper, we enumerated and characterized ex vivo Melan-A-specific cells in peripheral blood samples from both melanoma patients and healthy individuals. High frequencies (>/=1 in 2,500 CD8(+) T cells) of Melan-A-specific cells were found in 10 out of 13 patients, and, surprisingly, in 6 out of 10 healthy individuals. Virtually all Melan-A-specific cells from 6 out of 6 healthy individuals and from 7 out of 10 patients displayed a naive CD45RA(hi)/RO(-) phenotype, whereas variable proportions of Ag-experienced CD45RA(lo)/RO(+) Melan-A-specific cells were observed in the remaining 3 patients. In contrast, ex vivo influenza matrix-specific CTLs from all individuals exhibited a CD45RA(lo)/RO(+) memory phenotype as expected. Ag specificity of tetramer-sorted A2/Melan-A(+) cells from healthy individuals was confirmed after mitogen-driven expansion. Likewise, functional limiting dilution analysis and interferon gamma ELISPOT assays independently confirmed that most of the Melan-A-specific cells were not Ag experienced. Thus, it appears that high frequencies of naive Melan-A-specific CD8(+) T cells can be found in a large proportion of HLA-A*0201(+) individuals. Furthermore, as demonstrated for one patient followed over time, dramatic phenotype changes of circulating Melan-A-specific cells can occur in vivo.