Melanoma antigen-A11 (MAGE-A11) is a proto-oncogene involved in androgen receptor signaling and androgen-dependent cell growth. In this report we provide evidence that MAGE-A11 interacts with Skp2 (S phase kinase-associated protein), the substrate recognition protein of the Skp1-Cullin1-F-box E3 ubiquitin ligase, and with Skp2 binding protein, cyclin A. A similar cyclin A binding motif in MAGE-A11 and Skp2 was consistent with a competitive relationship between MAGE-A11 and Skp2 in binding cyclin A. Skp2 inhibited MAGE-A11 interaction with cyclin A. Differential effects of MAGE-A11 on Skp2-mediated protein degradation were also revealed. MAGE-A11 increased Skp2-mediated degradation of cyclin A and retinoblastoma-related protein p130. In contrast, MAGE-A11 decreased Skp2-mediated degradation of E2F1 and Skp2 self-ubiquitination. Stabilization of E2F1 by MAGE-A11 was associated with sequestration and inactivation of Skp2 through the formation of an E2F1-MAGE-A11-Skp2 complex. We conclude that direct interactions of MAGE-A11 with Skp2 and cyclin A regulate the substrate-specificity of Skp2-mediated protein degradation.