Abstract Purpose: The progressive immune dysfunctions that occur in patients with advanced melanoma make them unlikely to efficiently respond to cancer vaccines. A multicenter randomized phase II trial was conducted to test whether immunization with modified HLA class I tumor peptides in the context of adjuvant therapy results in better immunologic responses and improved clinical outcomes in patients with early melanoma (stages IIB/C-III). Experimental Design: Forty-three patients were enrolled to undergo vaccination (n = 22) or observation (n = 21). The vaccine included four HLA-A*0201–restricted modified peptides (Melan-A/MART-1[27L], gp100[210M], NY-ESO-1[165V], and Survivin[97M]) emulsified in Montanide ISA51 and injected subcutaneously in combination with cyclophosphamide (300 mg/m2) and low-dose IL-2 (3 × 106 IU). The immune responses were monitored using ex vivo IFN-γ–ELISpot, HLA/multimer staining, and in vitro short-term peptide sensitization assays. Results: Vaccination induced a rapid and persistent increase in specific effector memory CD8+ T cells in 75% of the patients. However, this immunization was not associated with any significant increase in disease-free or overall survival as compared with the observation group. An extensive immunologic analysis revealed a significantly reduced cross-recognition of the corresponding native peptides and, most importantly, a limited ability to react to melanoma cells. Conclusions: Adjuvant setting is an appealing approach for testing cancer vaccines because specific CD8+ T cells can be efficiently induced in most vaccinated patients. However, the marginal antitumor activity of the T cells induced by modified peptides in this study largely accounts for the observed lack of benefit of vaccination. These findings suggest reconsidering this immunization strategy, particularly in early disease. Clin Cancer Res; 18(23); 6485–96. ©2012 AACR.