The yeast cyclin-C–Cdk8p kinase complex represses the transcription of a subset of genes involved in the stress response. To relieve this repression, cyclin C is destroyed in cells exposed to H2O2 by the 26S proteasome. This report identifies Not4p as the ubiquitin ligase mediating H2O2-induced cyclin C destruction. Not4p is required for H2O2-induced cyclin C destruction in vivo and polyubiquitylates cyclin C in vitro by utilizing Lys48, a ubiquitin linkage associated with directing substrates to the 26S proteasome. Before its degradation, cyclin C, but not Cdk8p, translocates from the nucleus to the cytoplasm. This translocation requires both the cell-wall-integrity MAPK module and phospholipase C, and these signaling pathways are also required for cyclin C destruction. In addition, blocking cytoplasmic translocation slows the mRNA induction kinetics of two stress response genes repressed by cyclin C. Finally, a cyclin C derivative restricted to the cytoplasm is still subject to Not4p-dependent destruction, indicating that the degradation signal does not occur in the nucleus. These results identify a stress-induced proteolytic pathway regulating cyclin C that requires nuclear to cytoplasmic relocalization and Not4p-mediated ubiquitylation.