The innate immune system is able to build memory-like features in response to certain infections or vaccines, resulting in enhanced responsiveness upon (re)challenge with the same or an unrelated pathogen, a phenomenon termed ‘trained immunity'. Compared with antigen-dependent adaptive immune responses triggered by classical vaccines against specific pathogens, trained immunity-related vaccines induce enhanced innate immune responses against unrelated pathogens and provide ‘heterologous protection'. Here, we discuss the heterologous effects of vaccines against infections and detail the latest insights into the cellular and molecular mechanisms mediating trained immunity. Additionally, novel vaccine strategies are suggested for fighting new pandemics in the future by taking advantage of the heterologous memory features of trained immunity.