Since both tumor cells and host immune cell repertoires are diverse and heterogeneous, immune responses against tumor-associated antigens should differ substantially among individual cancer patients. Selection of suitable peptide vaccines for individual patients based on the preexisting host immunity before vaccination could induce potent anti-tumor responses that provide clinical benefit to cancer patients. We have developed a novel immunotherapeutic approach of personalized peptide vaccination (PPV) in which a maximum of four human leukocyte antigen (HLA) class IA-matched peptides are selected for vaccination among pooled peptides on the basis of both HLA class IA type and the preexisting host immunity before vaccination. In this review, we discuss our recent results of preclinical and clinical studies of PPV for various types of advanced cancer.