Molecular mechanisms enabling the switching and maintenance of epigenetic states are not fully understood. Distinct histone modifications are often associated with ON/OFF epigenetic states, but how these states are stably maintained through DNA replication, yet in certain situations switch from one to another remains unclear. Here, we address this problem through identification of Arabidopsis INCURVATA11 (ICU11) as a Polycomb Repressive Complex 2 accessory protein. ICU11 robustly immunoprecipitated in vivo with PRC2 core components and the accessory proteins, EMBRYONIC FLOWER 1 (EMF1), LIKE HETEROCHROMATIN PROTEIN1 (LHP1), and TELOMERE_REPEAT_BINDING FACTORS (TRBs). ICU11 encodes a 2-oxoglutarate-dependent dioxygenase, an activity associated with histone demethylation in other organisms, and mutant plants show defects in multiple aspects of the Arabidopsis epigenome. To investigate its primary molecular function we identified the Arabidopsis FLOWERING LOCUS C (FLC) as a direct target and found icu11 disrupted the cold-induced, Polycomb-mediated silencing underlying vernalization. icu11 prevented reduction in H3K36me3 levels normally seen during the early cold phase, supporting a role for ICU11 in H3K36me3 demethylation. This was coincident with an attenuation of H3K27me3 at the internal nucleation site in FLC, and reduction in H3K27me3 levels across the body of the gene after plants were returned to the warm. Thus, ICU11 is required for the cold-induced epigenetic switching between the mutually exclusive chromatin states at FLC, from the active H3K36me3 state to the silenced H3K27me3 state. These data support the importance of physical coupling of histone modification activities to promote epigenetic switching between opposing chromatin states.