Improved understanding of cancer immunology has gradually brought increasing attention towards cancer-preventive vaccines as an important tool in the fight against cancer. The aim of this approach is to reduce cancer occurrence by inducing a specific immune response targeting tumours at an early stage before they can fully develop. The great advantage of preventive cancer vaccines lies in the potential to harness a less-compromised immune system in vaccine recipients before their immune responses become affected by the advanced status of the disease itself or by aggressive treatments such as chemotherapy. Successful implementation of immunoprevention against oncogenic viruses such as hepatitis B and papillomavirus has led to a dramatic decrease in virally induced cancers. Extending this approach to other cancers holds great promise but remains a major challenge. Here, we provide a comprehensive review of preclinical evidence supporting this approach, encouraging results from pioneering clinical studies as well as a discussion on the key aspects and open questions to address in order to design potent prophylactic cancer vaccines in the near future.