Refractory bone and soft tissue sarcomas are challenging diseases to treat because of their robustness to chemotherapy. Although cancer vaccines have the potential to become an attractive treatment modality, their progress has been hampered by the presence of many subtypes of sarcomas and different human leukocyte antigen (HLA)-types. We investigated whether personalized peptide vaccination (PPV) would be feasible for the vast majority of sarcoma patients. Twenty refractory bone and soft tissue sarcoma patients with nine different subtypes and 11 different HLA-class IA phenotypes were enrolled in this study. A maximum of four HLA-matched peptides showing higher peptide-specific IgG responses in pre-vaccination plasma were selected from 31 pooled peptide candidates applicable for the HLA-A2, -A3, -A11, -A24, -A26, -A31, and -A33 types, and were subcutaneously administered weekly for 6 weeks and bi-weekly thereafter. Measurement of peptide-specific CTL and IgG responses along with other laboratory analyses were conducted before and after vaccination. No patients were excluded by either sarcoma subtypes or different HLA-types. No severe adverse events associated with PPV were observed in any patients. Peptide-specific immunological boosting was observed in the post-vaccination samples from the majority of patients. Tumor reduction of the lung metastasis and a long stable disease was observed in each case, and the median overall survival time of the 20 cases was 9.6 months. Taken together, PPV could be feasible for the vast majority of refractory sarcoma patients because of the safety and higher rates of immunological responses regardless of the presence of different sarcoma subtypes and various HLA-types.