Transcriptional memory is critical for the faster reactivation of necessary genes upon environmental changes and requires that the genes were previously in an active state. However, whether transcriptional repression also displays 'memory' of the prior transcriptionally inactive state remains unknown. In this study, we show that transcriptional repression of ∼540 genes in yeast occurs much more rapidly if the genes have been previously repressed during carbon source shifts. This novel transcriptional response has been termed transcriptional repression memory (TREM). Interestingly, Rpd3L histone deacetylase (HDAC), targeted to active promoters induces TREM. Mutants for Rpd3L exhibit increased acetylation at active promoters and delay TREM significantly. Surprisingly, the interaction between H3K4me3 and Rpd3L via the Pho23 PHD finger is critical to promote histone deacetylation and TREM by Rpd3L. Therefore, we propose that an active mark, H3K4me3 enriched at active promoters, instructs Rpd3L HDAC to induce histone deacetylation and TREM.