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 γ 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.