Epigenetic inheritance of gene expression states enables a single genome to maintain distinct cellular identities. How histone modifications contribute to this process remains unclear. Using global chromatin perturbations and local, time-controlled modulation of transcription, we establish the existence of epigenetic memory of transcriptional activation for genes that can be silenced by the Polycomb group. This property emerges during cell differentiation and allows genes to be stably switched after a transient transcriptional stimulus. This transcriptional memory state at Polycomb targets operates in cis; however, rather than relying solely on read-and-write propagation of histone modifications, the memory is also linked to the strength of activating inputs opposing Polycomb proteins, and therefore varies with the cellular context. Our data and computational simulations suggest a model whereby transcriptional memory arises from double-negative feedback between Polycomb-mediated silencing and active transcription. Transcriptional memory at Polycomb targets thus depends not only on histone modifications but also on the gene-regulatory network and underlying identity of a cell.