The insight that the immune system is involved in tumor resistance is gaining momentum and this has led to the development of immunotherapeutic strategies aiming at enhancement of immune-mediated tumor destruction. Although some of these strategies have moderate clinical benefit, most stand-alone therapies fail to significantly affect progressive disease and survival or do so only in a minority of patients. Research on the mechanisms underlying the generation of immune responses against tumors and the immune evasion by tumors has emphasized that various mechanisms simultaneously prevent effective immunity against cancer including inefficient presentation of tumor antigens by dendritic cells and induction of negative immune regulation by regulatory T-cells (Tregs) and myeloid derived suppressor cells (MDSCs). Thus the design of therapies that simultaneously improve effective tumor immunity and counteract immune evasion by tumors seems most desirable for clinical efficacy. As it is unlikely that a single immunotherapeutic strategy addresses all necessary requirements, combinatorial strategies that act synergistically need to be developed. Here we discuss the current knowledge and prospects of treatment with synthetic peptide vaccines that stimulate tumor-specific T-cell responses combined with adjuvants, immune modulating antibodies, cytokines and chemotherapy. We conclude that combinatorial approaches have the best potency to accomplish the most significant tumor destruction but further research is required to optimize such approaches.