Purpose: To measure the CD8+ T-cell response to a melanoma peptide vaccine and to compare an every-2-weeks with an every-3-weeks vaccination schedule. Patients and Methods: Thirty HLA-A2-positive patients with resected stage I to III melanoma were randomly assigned to receive vaccinations every 2 weeks (13 vaccines) or every 3 weeks (nine vaccines) for 6 months. The synthetic, modified gp100 peptide, g209-2M, and a control peptide, HPV16 E7, were mixed in incomplete Freund's adjuvant and injected subcutaneously. Peripheral blood mononuclear cells obtained before and after vaccination by leukapheresis were analyzed using a fluorescence-based HLA/peptide-tetramer binding assay and cytokine flow cytometry. Results: Vaccination induced an increase in peptide-specific T cells in 28 of 29 patients. The median frequency of CD8+ T cells specific for the g209-2M peptide increased markedly from 0.02% before to 0.34% after vaccination (P < .0001). Eight patients (28%) exhibited peptide-specific CD8+ T-cell frequencies greater than 1%, including two patients with frequencies of 4.96% and 8.86%, respectively. Interferon alfa-2b-treated patients also had significant increases in tetramer-binding cells (P < .0001). No difference was observed between the every-2-weeks and the every-3-weeks vaccination schedules (P = .59). Conclusion: Flow cytometric analysis of HLA/peptide-tetramer binding cells was a reliable means of quantifying the CD8+ T-cell response to peptide immunization. This assay may be suitable for use in future trials to optimize different vaccination strategies. Concurrent interferon treatment did not inhibit the development of a peptide-specific immune response and vaccination every 2 weeks, and every 3 weeks produced similar results.