Plants and animals/humans have evolved sophisticated innate immune systems to cope with microbial attack. Innate immunity implies the presence of membrane-located and intracellular receptors to recognize compounds released by damage or by invading pathogens. After detection the receptor molecules initiate intracellular defense signaling, resulting in cell death and/or production of defense molecules. Interestingly, the defense response includes also memory mechanisms, which allow the organisms to better cope with future microbial attacks. Redox mechanisms play an important role in defense signaling. In this review article, we compare the innate immune memory of animals/humans and plants and describe how reversible nitric oxide- and reactive oxygen species-dependent protein modifications enable the activation of defense signaling proteins and transcription factors and regulate the activity of chromatin modifying enzymes to establish innate immune memory. We hope to encourage efforts to characterize further molecular redox mechanisms of the innate immune memory, which might enable the development of new immunotherapies.