There is no standard treatment modality for advanced gastric cancer (GC) at the present time. To develop a new treatment modality, we investigated the immunological responses of advanced GC patients (n = 13, 9 non-scirrhous and 4 scirrhous types) vaccinated with peptides to a regimen under which pre-vaccination peripheral blood mononuclear cells (PBMCs) were screened for their reactivity in vitro to each of 14 peptides on HLA-A24 or 16 peptides on -A2 allele, then only the reactive peptides (maximum: 4) were administered in vivo. This regimen was generally well tolerated, although grade I levels of fever and local skin reactions were observed in several patients. Delayed-type hypersensitivity (DTH) to the vaccinated peptides was observed in 4 patients. Increased cellular and humoral immune responses to the vaccinated peptides were observed in post-vaccination PBMCs from 4 of 8 patients and in post-vaccination sera of 8 of 10 patients tested, respectively. Prolonged survival was observed in patients showing cellular and humoral immune responses to the vaccinated peptides in the post-vaccination samples, including all 4 patients with the scirrhous type. These results encourage further development of peptide-based immunotherapy for GC patients.