The three PRL (phosphatases of regenerating liver) protein tyrosine phosphatases (PRL-1,-2 and-3) have been identified as key contributors to metastasis in several human cancers, yet the molecular basis of their pro-oncogenic property is unclear. Among the subfamily of PRL phosphatases, overexpression of PRL-2 in breast cancer cells has been shown to promote tumor growth by a mechanism that remains to be uncovered. Here we show that PRL-2 regulates intracellular magnesium levels by forming a functional heterodimer with the magnesium transporter CNNM3. We further reveal that CNNM3 is not a phosphorylated substrate of PRL-2, and that the interaction occurs through a loop unique to the CBS pair domains of CNNM3 that exists only in organisms having PRL orthologs. Supporting the role of PRL-2 in cellular magnesium transport is the observation that PRL-2 knockdown results in a substantial decrease of cellular magnesium influx. Furthermore, in PRL-2 knockout mice, serum magnesium levels were significantly elevated as compared with control animals, indicating a pivotal role for PRL-2 in regulating cellular magnesium homeostasis. Although the expression levels of CNNM3 remained unchanged after magnesium depletion of various cancer cell lines, the interaction between endogenous PRL-2 and CNNM3 was markedly increased. Importantly, xenograft tumor assays with CNNM3 and a mutant form that does not associate with PRL-2 confirm that CNNM3 is itself pro-oncogenic, and that the PRL-2/CNNM3 association is important for conferring transforming activities. This finding is further confirmed from data in human breast cancer tissues showing that CNNM3 levels correlate positively with both PRL-2 expression and the tumor proliferative index. In summary, we demonstrate that oncogenic PRL-2 controls tumor growth by modulating intracellular magnesium levels through binding with the CNNM3 magnesium transporter.