The inability of innate immunity to build an immunological memory, considered one of the main characteristics differentiating it from adaptive immunity, has been recently challenged by studies in plants, invertebrates, and mammals. Long-term reprogramming of innate immunity, that induces adaptive traits and has been termed trained immunity characterizes prototypical innate immune cells such as natural killer cells and monocytes, and provides protection against reinfection in a T/B-cell-independent manner. In contrast, trained immunity has been shown to be able to induce protection against reinfection in a lymphocyte-independent manner. Non-specific protective effects dependent on trained immunity have also been shown to be induced after BCG vaccination in humans. Specific signaling mechanisms including the dectin-1/Raf1 and NOD2-mediated pathways induce trained immunity, through induction of histone modifications (methylation, acetylation) and epigenetic reprogramming of monocyte function. Complex immunological and metabolic circuits link cell stimulation to a long-term epigenetic reprogramming of its function. The concept of trained immunity represents a paradigm change in immunity and its putative role in infection and inflammation may represent the next step in the design of future vaccines and immunotherapeutic approaches.