Epigenetic inheritance models posit that during Polycomb repression, Polycomb repressive complex 2 (PRC2) propagates histone H3 lysine 27 trimethylation (H3K27me3) independently of DNA sequence. We show that insertion of Polycomb response element (PRE) DNA into the Drosophila genome creates extended domains of H3K27me3-modified nucleosomes in the flanking chromatin and causes repression of a linked reporter gene. After excision of PRE DNA, H3K27me3 nucleosomes become diluted with each round of DNA replication, and reporter gene repression is lost. After excision in replication-stalled cells, H3K27me3 levels stay high and repression persists. H3K27me3-marked nucleosomes therefore provide a memory of repression that is transmitted in a sequence-independent manner to daughter strand DNA during replication. In contrast, propagation of H3K27 trimethylation to newly incorporated nucleosomes requires sequence-specific targeting of PRC2 to PRE DNA.