Vaccines have classically been used for disease prevention. Modern clinical vaccines are continuously being developed for both traditional use as well as for new applications. Typically thought of in terms of infectious disease control, vaccination approaches can alternatively be adapted as a cancer therapy. Vaccines targeting cancer antigens can be used to induce anti-tumour immunity and have demonstrated therapeutic efficacy both pre-clinically and clinically. Various approaches now exist and further establish the tremendous potential and adaptability of anti-cancer vaccination. Classical strategies include ex vivo-loaded immune cells, RNA- or DNA-based vaccines and tumour cell lysates. Recent oncolytic virus development has resulted in a surge of novel viruses engineered to induce powerful tumour-specific immune responses. In addition to their use as cancer vaccines, oncolytic viruses have the added benefit of being directly cytolytic to cancer cells and thus promote antigen recognition within a highly immune-stimulating tumour microenvironment. While oncolytic viruses are perfectly equipped for efficient immunization, this complicates their use upon previous exposure. Indeed, the host’s anti-viral counter-attacks often impair multiple-dosing regimens. In this review we will focus on the use of oncolytic viruses for anti-tumour vaccination. We will explore different strategies as well as ways to circumvent some of their limitations.