Training-dependent increases in c-fos have been used to identify engram cells encoding long-term memories (LTMs). However, the interaction between transcription factors required for LTM, including CREB and c-Fos, and activating kinases such as phosphorylated ERK (pERK) in the establishment of memory engrams has been unclear. Formation of LTM of an aversive olfactory association in flies requires repeated training trials with rest intervals between trainings. Here, we find that prolonged rest interval-dependent increases in pERK induce transcriptional cycling between c-Fos and CREB in a subset of KCs in the mushroom bodies, where olfactory associations are made and stored. Preexisting CREB is required for initial c-fos induction, while c-Fos is required later to increase CREB expression. Blocking or activating c-fos-positive engram neurons inhibits memory recall or induces memory-associated behaviors. Our results suggest that c-Fos/CREB cycling defines LTM engram cells required for LTM.