Long noncoding RNAs (lncRNAs) have been proposed to play important roles in gene regulation. However, their importance in epigenetic silencing and how specificity is determined remain controversial. We have investigated the cold-induced epigenetic switching mechanism involved in the silencing of Arabidopsis thaliana Flowering Locus C (FLC), which occurs during vernalization. Antisense transcripts, collectively named COOLAIR, are induced by prolonged cold before the major accumulation of histone 3 lysine 27 trimethylation (H3K27me3), characteristic of Polycomb silencing. We have found that COOLAIR is physically associated with the FLC locus and accelerates transcriptional shutdown of FLC during cold exposure. Removal of COOLAIR disrupted the synchronized replacement of H3K36 methylation with H3K27me3 at the intragenic FLC nucleation site during the cold. Consistently, genetic analysis showed COOLAIR and Polycomb complexes work independently in the cold-dependent silencing of FLC. Our data reveal a role for lncRNA in the coordinated switching of chromatin states that occurs during epigenetic regulation.