Melanoma antigen A (MAGE-A) proteins comprise a structurally and biochemically similar sub-family of Cancer/Testis antigens that are expressed in many cancer types and are thought to contribute actively to malignancy. MAGE-A proteins are established regulators of certain cancer-associated transcription factors, including p53, and are activators of several RING finger-dependent ubiquitin E3 ligases. Here, we show that MAGE-A2 associates with MDM2, a ubiquitin E3 ligase that mediates ubiquitylation of more than 20 substrates including mainly p53, MDM2 itself, and MDM4, a potent p53 inhibitor and MDM2 partner that is structurally related to MDM2. We find that MAGE-A2 interacts with MDM2 via the N-terminal p53-binding pocket and the RING finger domain of MDM2 that is required for homo/hetero-dimerization and for E2 ligase interaction. Consistent with these data, we show that MAGE-A2 is a potent inhibitor of the E3 ubiquitin ligase activity of MDM2, yet it does not have any significant effect on p53 turnover mediated by MDM2. Strikingly, however, increased MAGE-A2 expression leads to reduced ubiquitylation and increased levels of MDM4. Similarly, silencing of endogenous MAGE-A expression diminishes MDM4 levels in a manner that can be rescued by the proteasomal inhibitor, bortezomid, and permits increased MDM2/MDM4 association. These data suggest that MAGE-A proteins can: (i) uncouple the ubiquitin ligase and degradation functions of MDM2; (ii) act as potent inhibitors of E3 ligase function; and (iii) regulate the turnover of MDM4. We also find an association between the presence of MAGE-A and increased MDM4 levels in primary breast cancer, suggesting that MAGE-A-dependent control of MDM4 levels has relevance to cancer clinically.