Eukaryotic cells control their proteome by regulating protein production and protein clearance. Protein production is determined to a large extent by mRNA levels, whereas protein degradation depends mostly upon the proteasome. Dysfunction of the proteasome leads to the accumulation of non-functional proteins that can aggregate, be toxic for the cell, and, in extreme cases, lead to cell death. mRNA levels are controlled by their rates of synthesis and degradation. Recent evidence indicates that these rates have oppositely co-evolved to ensure appropriate mRNA levels. This opposite co-evolution has been correlated with the mutations in the Ccr4-Not complex. Consistently, the deadenylation enzymes responsible for the rate-limiting step in eukaryotic mRNA degradation, Caf1 and Ccr4, are subunits of the Ccr4-Not complex. Another subunit of this complex is a RING E3 ligase, Not4. It is essential for cellular protein solubility and has been proposed to be involved in co-translational quality control. An open question has been whether this role of Not4 resides strictly in the regulation of the deadenylation module of the Ccr4-Not complex. However, Not4 is important for proper assembly of the proteasome, and the Ccr4-Not complex may have multiple functional modules that participate in protein quality control in different ways. In this work we studied how the functions of the Caf1/Ccr4 and Not4 modules are connected. We concluded that Not4 plays a role in protein quality control independently of the Ccr4 deadenylase, and that it is involved in clearance of aberrant proteins at least in part via the proteasome.