Since the identification of tumor associated antigens (TAA) in different tumor histotypes, many vaccination strategies have been investigated, including peptide-based vaccines. Results from the first decade of clinical experimentation, though demonstrating the feasibility and the good toxicity profile of this approach, provided evidence of clinical activity only in a minority of patients, despite inducing immunization in up to 50% of them. In this review, we discuss the different approaches recently developed in order to induce stronger peptide-induced immune-mediated tumor growth control, possibly translating into improved clinical response rates, with specific focus on multipeptide-based anti-cancer vaccines. This strategy offers many advantages, such as the possibility of bypassing tumor heterogeneity and selection of antigen (Ag)-negative clones escaping peptide-specific immune responses, or combining HLA class I- and class II-restricted epitopes, thus eliciting both CD4- and CD8-mediated immune recognition. Notably, advances in Ag discovery technologies permit further optimization of peptide selection, in terms of identification of tumor-specific and unique TAA as well as Ags derived from different tumor microenvironment cell components. With the ultimate goal of combining peptide selection with patient-specific immunogenic profile, peptide based anti-cancer vaccines remain a promising treatment for cancer patients, as attested by of pre-clinical and clinical studies.