Gene silencing by Polycomb complexes is central to eukaryotic development. Cold-induced epigenetic repression of FLOWERING LOCUS C (FLC) in the plant Arabidopsis provides 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 within FLC, 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 at FLC thus has mechanistically distinct phases, which involve specialization of distinct Polycomb components to deliver first metastable then long-term epigenetic silencing.