Gene silencing by Polycomb complexes is central to eukaryotic development. Cold-induced epigenetic repression ofFLOWERING LOCUS C(FLC) in the plantArabidopsisprovides an opportunity to study initiation and maintenance of Polycomb silencing. Here, we show that a subset of Polycomb repressive complex 2 factors nucleate silencing in a small region withinFLC, locally increasing H3K27me3 levels. This nucleation confers a silenced state that is metastably inherited, with memory held in the local chromatin. Metastable memory is then converted to stable epigenetic silencing through separate Polycomb factors, which spread across the locus after cold to enlarge the domain that contains H3K27me3. Polycomb silencing atFLCthus has mechanistically distinct phases, which involve specialization of distinct Polycomb components to deliver first metastable then long-term epigenetic silencing.