Evolution of the mammalian sex chromosomes has resulted in a heterologous X and Y pair, where the Y chromosome has lost most of its genes. Hence, there is a need for X-linked gene dosage compensation between XY males and XX females. In placental mammals, this is achieved by random inactivation of one X chromosome in all female somatic cells. Upregulation of Xist transcription on the future inactive X chromosome acts against Tsix antisense transcription, and spreading of Xist RNA in cis triggers epigenetic changes leading to X-chromosome inactivation. Previously, we have shown that the X-encoded E3 ubiquitin ligase RNF12 is upregulated in differentiating mouse embryonic stem cells and activates Xist transcription and X-chromosome inactivation. Here we identify the pluripotency factor REX1 as a key target of RNF12 in the mechanism of X-chromosome inactivation. RNF12 causes ubiquitination and proteasomal degradation of REX1, and Rnf12 knockout embryonic stem cells show an increased level of REX1. Using chromatin immunoprecipitation sequencing, REX1 binding sites were detected in Xist and Tsix regulatory regions. Overexpression of REX1 in female embryonic stem cells was found to inhibit Xist transcription and X-chromosome inactivation, whereas male Rex1(+/-) embryonic stem cells showed ectopic X-chromosome inactivation. From this, we propose that RNF12 causes REX1 breakdown through dose-dependent catalysis, thereby representing an important pathway to initiate X-chromosome inactivation. Rex1 and Xist are present only in placental mammals, which points to co-evolution of these two genes and X-chromosome inactivation.