Immunological memory is a crucial part of the immune defense that allows organisms to respond against previously encountered pathogens or other harmful factors. Immunological memory is based on the establishment of epigenetic modifications of the genome. The ability to memorize encounters with pathogens and other harmful factors and mount enhanced defense upon subsequent encounters is an evolutionarily ancient mechanism operating in all animals and plants. However, the term immunological memory is usually restricted to the organisms (invertebrates and vertebrates) possessing the immune system. The mammalian immune system, with innate and adaptive branches, is the most sophisticated among vertebrates. The concept of innate memory and memory macrophages is relatively new and thus understudied. We introduce the concept of immunological memory and describe types of memory in different species and their evolutionary status. We discuss why the traditional view of innate immune cells as the first-line defenders is too restrictive and how the innate immune cells can accumulate and retain immunologic memory. We describe how the initial priming leads to chromatin remodeling and epigenetic changes, which allow memory macrophage formation. We also summarize what is currently known about the mechanisms underlying development of memory macrophages; their molecular and metabolic signature and surface markers; and how they may contribute to immune defense, diseases, and organ transplantation.