The SMC5-6 protein complex is involved in the cellular response to DNA damage. It is composed of 6 - 8 polypeptides, of which Nse1, Nse3 and Nse4 form a tight sub-complex. MAGEG1, the mammalian ortholog of Nse3, is the founding member of the MAGE (melanoma-associated antigen) protein family and Nse4 is related to the EID (E1A-like inhibitor of differentiation) family of transcriptional repressors. We have identified a conserved hydrophobic surface on the C-terminal domain of Nse3 that interacts with Nse4 and identified residues in its N-terminal domain that are essential for interaction with Nse1. We show that these interactions are conserved in the human orthologs. In an examination of the evolutionary conservation of the Nse3-Nse4 interactions, we find that most MAGE proteins can interact with at least one of the NSE4/EID proteins.