Challenge with specific microbial stimuli induces long lasting epigenetic changes in innate immune cells that result in their enhanced response to a second challenge by the same or unrelated microbial insult, a process referred to as trained immunity. This opens a new avenue in vaccinology to develop Trained Immunity-based Vaccines (TIbV), defined as vaccine formulations that induce training in innate immune cells. Unlike conventional vaccines, which are aimed to elicit only specific responses to vaccine-related antigens, TIbV aim to stimulate broader responses. As trained immunity is generally triggered by pattern recognition receptors (PRRs), TIbV should be formulated with microbial structures containing suitable PRR-ligands. The TIbV concept we describe here may be used for the development of vaccines focused to promote host resistance against a wide spectrum of pathogens. Under the umbrella of trained immunity, a broad protection can be achieved by: (i) increasing the nonspecific effector response of innate immune cells (e.g., monocyte/macrophages) to pathogens, (ii) harnessing the activation state of dendritic cells to enhance adaptive T cell responses to both specific and nonrelated (bystander) antigens. This capacity of TIbV to promote responses beyond their nominal antigens may be particularly useful when conventional vaccines are not available or when multiple coinfections and/or recurrent infections arise in susceptible individuals. As the set of PRR-ligands chosen is essential not only for stimulating trained immunity but also to drive adaptive immunity, the precise design of TIbV will improve with the knowledge on the functional relationship among the different PRRs. While the TIbV concept is emerging, a number of the current anti-infectious vaccines, immunostimulants, and even vaccine adjuvants may already fall in the TIbV category. This may apply to increase immunogenicity of novel vaccine design approaches based on small molecules, like those achieved by reverse vaccinology.