The regulation of protein and mRNA turnover is essential for many cellular processes. We recently showed that ubiquitin--traditionally linked to protein degradation--directly regulates the degradation of mRNAs through the action of a newly identified family of RNA-binding E3 ubiquitin ligases. How ubiquitin regulates mRNA decay remains unclear. Here, we identify a new role for ubiquitin in regulating deadenylation, the initial and often rate-limiting step in mRNA degradation. MEX-3C, a canonical member of this family of RNA-binding ubiquitin ligases, associates with the cytoplasmic deadenylation complexes and ubiquitinates CNOT7(Caf1), the main catalytic subunit of the CCR4-NOT deadenylation machinery. We establish a new role for ubiquitin in regulating MHC-I mRNA deadenylation as ubiquitination of CNOT7 by MEX-3C regulates its deadenylation activity and is required for MHC-I mRNA degradation. Since neither proteasome nor lysosome inhibitors rescued MEX-3C-mediated MHC-I mRNA degradation, our findings suggest a new non-proteolytic function for ubiquitin in the regulation of mRNA decay.