Posttranslational protein modification with small ubiquitin-related modifier (SUMO) is an important regulatory mechanism implicated in many cellular processes, including several of biomedical relevance. We report that inhibition of the proteasome leads to accumulation of proteins that are simultaneously conjugated to both SUMO and ubiquitin in yeast and in human cells. A similar accumulation of such conjugates was detected in Saccharomyces cerevisiae ubc4 ubc5 cells as well as in mutants lacking two RING finger proteins, Ris1 and Hex3/Slx5-Slx8, that bind to SUMO as well as to the ubiquitin-conjugating enzyme Ubc4. In vitro, Hex3-Slx8 complexes promote Ubc4-dependent ubiquitylation. Together these data identify a previously unrecognized pathway that mediates the proteolytic down-regulation of sumoylated proteins. Formation of substrate-linked SUMO chains promotes targeting of SUMO-modified substrates for ubiquitin-mediated proteolysis. Genetic and biochemical evidence indicates that SUMO conjugation can ultimately lead to inactivation of sumoylated substrates by polysumoylation and/or ubiquitin-dependent degradation. Simultaneous inhibition of both mechanisms leads to severe phenotypic defects.