More than many other fields in medicine, cancer vaccine development has been plagued by a wide gap between the massive amounts of highly encouraging preclinical data on one hand, and the disappointing clinical results on the other. It is clear now that traditional approaches from the infectious diseases' vaccine field cannot be borrowed as such to treat cancer. This review highlights some of the strategies developed to improve vaccine formulations for oncology, including research into more powerful or "smarter" adjuvants to elicit anti-tumoral cellular immune responses. As an illustration of the difficulties in translating smart preclinical strategies into real benefit for the cancer patient, the difficult road of vaccine development in lung cancer is given as example. Finally, an outline is provided of the combinatorial strategies that leverage the increasing knowledge on tumor-associated immune suppressive networks. Indeed, combining with drugs that target the dominant immunosuppressive pathway in a given tumor promises to unlock the true power of cancer vaccines and potentially offer long-term protection from disease relapse.