Most vaccination studies of cancer patients find no clear association between clinical and immunological responses to the vaccine. We discuss the possible kinetics of the T cell response in melanoma patients against unique or shared tumor antigens. We hypothesize that a response against unique antigens prevails during primary melanoma growth, causing the selection of tumor cells lacking most of these antigens unless these are necessary to maintain the neoplastic state. After a subset of tumor cells metastasize to the lymph nodes, T cells are activated against previously ignored shared, differentiation-like antigens, owing to a new environment where pro-inflammatory cytokines can be present. The development of a T cell response to such normal epitopes then associates with tumor growth, but remains clinically inefficient. We predict that two immunologically different subsets of melanoma patients may exist, one that mounted an early immune response against melanoma antigens and one that did not. A paradox may emerge when vaccination is attempted in these two groups of subjects, with the second group being more prone to develop an effective immune response if the vaccine is potent enough to activate naive T cells, while the first has probably already eliminated most of the tumor antigens potentially recognizable by the host T cells owing to the previous selection made by the immune response developed early during tumor growth. Thus, it is likely that the subgroup of metastatic patients with a high frequency of anti-melanoma memory T cells may not show a clinical response to vaccination.