The polycomb repressive complex 2 (PRC2) regulates epigenetic gene repression in eukaryotes. Mechanisms controlling its developmental specificity and signal-responsiveness are poorly understood. Here, we identify an oxygen-sensitive N-terminal (N-) degron in the plant PRC2 subunit VERNALIZATION(VRN) 2, a homolog of animal Su(z)12, that promotes its degradation via the N-end rule pathway. We provide evidence that this N-degron arose early during angiosperm evolution via gene duplication and N-terminal truncation, facilitating expansion of PRC2 function in flowering plants. We show that proteolysis via the N-end rule pathway prevents ectopic VRN2 accumulation, and that hypoxia and long-term cold exposure lead to increased VRN2 abundance, which we propose may be due to inhibition of VRN2 turnover via its N-degron. Furthermore, we identify an overlap in the transcriptional responses to hypoxia and prolonged cold, and show that VRN2 promotes tolerance to hypoxia. Our work reveals a mechanism for post-translational regulation of VRN2 stability that could potentially link environmental inputs to the epigenetic control of plant development.