The mitochondrial phospholipid metabolism critically depends on members of the conserved Ups1/PRELI-like protein family in the intermembrane space. Ups1 and Ups2 (also termed Gep1) were shown to regulate the accumulation of cardiolipin (CL) and phosphatidylethanolamine (PE), respectively, in a lipid-specific but coordinated manner. It remained enigmatic, however, how the relative abundance of both phospholipids in mitochondrial membranes is adjusted on the molecular level. Here, we describe a novel regulatory circuit determining the accumulation of Ups1 and Ups2 in the intermembrane space. Ups1 and Ups2 are intrinsically unstable proteins, which are degraded by distinct mitochondrial peptidases. The turnover of Ups2 is mediated by the i-AAA protease Yme1, whereas Ups1 is degraded by both Yme1 and the metallopeptidase Atp23. We identified Mdm35, a member of the twin Cx(9)C protein family, as a novel interaction partner of Ups1 and Ups2. Binding to Mdm35 ensures import and protects both proteins against proteolysis. Homologues to all components of this pathway are present in higher eukaryotes, suggesting that the regulation of mitochondrial CL and PE levels is conserved in evolution.