Identification of antigenic peptides expressed on cancer cells enables us to treat cancer patients with peptide-based immunotherapy. Although optimal protocols for peptide-based vaccines have not yet been elucidated, boosting the immune system could be a better approach than priming the immune system to elicit prompt and potent peptide-specific T-cell responses in cancer patients. With this possibility in mind, the authors undertook a clinical trial in which cancer patients were vaccinated with peptides (maximum 4) after confirmation of pre-existing peptide-specific cytotoxic T-lymphocyte (CTL) precursors in the periphery. Fourteen patients (seven with melanoma and seven with other types of cancer) positive for either HLA-A24 or HLA-A2 were enrolled in this study. Fourteen and 16 peptides were used to screen for HLA-A24+ and HLA-A2+ patients, respectively. The vaccination was well tolerated, and the only adverse effects were local pain and fever. Kinetic analysis revealed that peptide-reactive CTLs increased after peptide vaccination in 7 of 14 patients. Immunoglobulin G (IgG) reactive to the administered peptides was detected in 2 patients before vaccination, although it became detectable in 8 of the other 12 patients after the peptide vaccination. Stable disease for more than 6 months was observed in five patients (one with melanoma and four with other types of cancer); all of these patients showed increased levels of peptide-specific IgG. These results indicate that peptide vaccination of patients showing evidence of pre-existing peptide-specific CTL precursors can be applied in further clinical trials aimed at the treatment of melanoma and other types of cancer.