Accumulating evidence suggests that transcriptional regulation is required for maintenance of long-term memories (LTMs). Here we characterize global transcriptional and epigenetic changes that occur during LTM storage in the Drosophila mushroom bodies (MBs), structures important for memory. Although LTM formation requires the CREB transcription factor and its coactivator, CBP, subsequent early maintenance requires CREB and a different coactivator, CRTC. Late maintenance becomes CREB independent and instead requires the transcription factor Bx. Bx expression initially depends on CREB/CRTC activity, but later becomes CREB/CRTC independent. The timing of the CREB/CRTC early maintenance phase correlates with the time window for LTM extinction and we identify different subsets of CREB/CRTC target genes that are required for memory maintenance and extinction. Furthermore, we find that prolonging CREB/CRTC-dependent transcription extends the time window for LTM extinction. Our results demonstrate the dynamic nature of stored memory and its regulation by shifting transcription systems in the MBs.