Immune responses in vertebrates are classically divided into innate and adaptive, with only the latter being able to build up immunological memory. However, although lacking adaptive immune responses, plants and invertebrates are protected against reinfection with pathogens, and invertebrates even display transplant rejection. In mammals, past "forgotten" studies demonstrate cross-protection between infections independently of T and B cells, and more recently memory properties for NK cells and macrophages, prototypical cells of innate immunity, have been described. We now posit that mammalian innate immunity also exhibits an immunological memory of past insults, for which we propose the term "trained immunity." Understanding trained immunity will revolutionize our view of host defense and immunological memory, and could lead to defining a new class of vaccines and immunotherapies.