RNA-binding E3 ubiquitin ligases were recently identified, though their function remains unclear. While studying the regulation of the MHC class I (MHC-I) pathway, we here characterize a novel role for ubiquitin in mRNA degradation. MHC-I molecules provide ligands for both cytotoxic T-lymphocytes as well as natural killer (NK) cells, and play a central role in innate and adaptive immunity. MHC-I cell-surface expression is closely monitored by NK cells, whose killer immunoglobulin-like receptors encode MHC-I-specific activatory and inhibitory receptors, implying that MHC-I expression needs to be tightly regulated. In a functional siRNA ubiquitome screen we identified MEX-3C, a novel RNA-binding ubiquitin E3 ligase, as responsible for the post-transcriptional, allotype-specific regulation of MHC-I. MEX-3C binds the 3'UTR of HLA-A2 mRNA, inducing its RING-dependent degradation. The RING domain of MEX-3C is not required for HLA-A2 cell-surface downregulation, but regulates the degradation of HLA-A2 mRNA. We have therefore uncovered a novel post-transcriptional pathway for regulation of HLA-A allotypes and provide a link between ubiquitination and mRNA degradation.