Deubiquitylating enzymes (DUBs) are a large group of proteases that regulate ubiquitin-dependent metabolic pathways by cleaving ubiquitin-protein bonds. Here we present a global study aimed at elucidating the effects DUBs have on protein abundance changes in eukaryotic cells. To this end we compare wild-type Saccharomyces cerevisiae to 20 DUB knock-out strains using quantitative proteomics to measure proteome-wide expression of isotope labeled proteins, and analyze the data in the context of known transcription-factor regulatory networks. Overall we find that protein abundances differ widely between individual deletion strains, demonstrating that removing just a single component from the complex ubiquitin system causes major changes in cellular protein expression. The outcome of our analysis confirms many of the known biological roles for characterized DUBs such as Ubp3p and Ubp8p, and we demonstrate that Sec28p is a novel Ubp3p substrate. In addition we find strong associations for several uncharacterized DUBs providing clues for their possible cellular roles. Hierarchical clustering of all deletion strains reveals pronounced similarities between various DUBs, which corroborate current DUB knowledge and uncover novel functional aspects for uncharacterized DUBs. Observations in our analysis support that DUBs induce both direct and indirect effects on protein abundances.