The epigenetic and functional reprogramming of immune genes during induction of trained immunity is accompanied by the metabolic rewiring of cellular state. This memory is induced in the hematopoietic niche and propagated to daughter cells, generating epigenetically and metabolically reprogrammed innate immune cells that are greatly enhanced in their capacity to resolve inflammation. In particular, these cells show accumulation of H3K4me3 and H3K27Ac epigenetic marks on multiple immune gene promoters and associated enhancers. However, the mechanism governing how these epigenetic marks accumulate at discrete immune gene loci has been poorly understood, until now. Here, we discuss some recent advances in the regulation of trained immunity, with a particular focus on the mechanistic role of a novel class of long non-coding RNAs in the establishment of epigenetic marks on trained immune gene promoters.