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 Drosophila gene, stuxnet (stx), that controls Pc protein stability. We find that heightened stx activity leads to homeotic transformation, reduced Pc activity, and de-repression of PcG targets. Conversely, stx mutants, which can be rescued by decreased Pc expression, display developmental defects resembling hyperactivation of Pc. Our biochemical analyses provide a mechanistic basis for the interaction between stx and Pc; 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 and induces homeotic transformation in Drosophila. Our results highlight an evolutionarily conserved mechanism of regulated protein degradation on PcG homeostasis and epigenetic activity.