Polycomb-group (PcG) proteins function to ensure correct deployment of developmental programs by epigenetically repressing target gene expression. Despite the importance, few studies have been focused on the regulation of PcG activity itself. Here, we report a novel Drosophila gene stuxnet (stx) that controls Pc protein stability. We find that heightened stx expression reduces Pc activity, leading to de-repression of PcG targets and homeotic transformation. Conversely, stx mutants display developmental defects associated with hyper-activation of Pc. Apart from its role on classical PcG targets, this Stx-controlled Pc activity is required for Notch signaling. Mechanistically, Stx facilitates Pc degradation in the proteasome independent of ubiquitin modification. Furthermore, this mode of regulation is conserved in vertebrates. Mouse stx promotes degradation of Cbx4, an orthologous Pc protein, in vertebrate cells, rescues stx-associated Notch defects and induces homeotic transformation in Drosophila. Our results highlight an evolutionarily conserved mechanism of regulated protein degradation on PcG homeostasis and epigenetic activity.