Recent clinical trials of peptide vaccine for cancer patients have rarely resulted in tumor regression. One of the reasons for this failure could be an insufficient induction of anti-tumor responses in these regimens, in which peptide-specific memory cytotoxic T lymphocytes (CTLs) were not measured prior to vaccination. We investigated in this study whether pre-vaccination measurement of peptide-specific CTLs can provide any advantages in lung cancer patients receiving peptide vaccination with regard to safety and immunological responses. Ten patients with advanced lung cancer received vaccination with peptides under a regimen of CTL precursor-oriented vaccination, in which pre-vaccination peripheral blood mononuclear cells (PBMCs) were at first screened for reactivity in vitro to each of 14 peptides, followed by in vivo administration of only the reactive peptides. Profiles of the vaccinated peptides varied markedly among the 10 patients. This regimen was generally well-tolerated, although local skin reactions, diarrhea, and colitis were observed in 8, 2, and 1 patient, respectively. Increased CTL responses against the immunized peptides and tumor cells were observed in the post-vaccination PBMCs from 4 of 8 and 3 of 10 patients tested, respectively. Peptide-specific IgG became detectable in post-vaccination sera in 4 of 10 patients tested, and these 4 patients had a long progression-free survival. Furthermore, the median survival time of 9 patients with non-small cell lung cancer was 668.0 +/- 164.2 days. These results encourage further development of CTL precursor-oriented peptide vaccination for lung cancer patients.