The family of cystathionine-β-synthase (CBS)-pair domain divalent metal cation transport mediators (CNNMs) is composed of four integral membrane proteins associated with Mg2+ transport. Structurally, CNNMs contain large cytosolic regions composed of a CBS-pair and a cyclic nucleotide-binding homology (CNBH) domain. How these regulate Mg2+ transport activity is unknown. Here, we determined the crystal structures of cytosolic fragments in two conformations: Mg2+-ATP-analog bound and ligand free. The structures reveal open and closed conformations with functionally important contacts not observed in structures of the individual domains. We also identified a second Mg2+-binding region in the CBS-pair domain and a different dimerization interface for the CNBH domain. Analytical ultracentrifugation and isothermal titration calorimetry experiments revealed a tight correlation between Mg2+-ATP binding and protein dimerization. Mutations that blocked either function prevented cellular Mg2+ efflux activity. The results suggest Mg2+ efflux is regulated by conformational changes associated with Mg2+-ATP binding to CNNM CBS-pair domains.