By providing ligands for Cytotoxic T-Lymphocytes (CTL) as well as Natural Killer (NK) cells, the HLA-A/B/C MHC class I molecules (MHC-I) play a central role in both innate and adaptive immunity. In addition to CTL-mediated recognition of MHC-peptide complexes, cell surface expression of MHC-I is closely monitored by NK cells, whose killer-cell immunoglobulin-like receptors encode activatory and inhibitory receptors with specificity for MHC-I. How the cell surface expression of MHC-I is tightly controlled is not well understood. In a functional siRNA ubiquitome screen to identify E3 ligases involved in MHC-I regulation we recently found that MEX-3C, a novel RNA-binding ubiquitin E3 ligase, is responsible for the post-transcriptional, HLA-A allotype-specific regulation of MHC-I. MEX-3C expression is increased upon NK cell activation and modulates the threshold of killing by these cells. We find that MEX-3C binds the 3′-untranslated region 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 direct link between ubiquitination and mRNA decay.