Rhomboids are a family of intramembrane serine proteases that are conserved in bacteria, archaea, and eukaryotes. They are required for numerous fundamental cellular functions such as quorum sensing, cell signaling, and mitochondrial dynamics. Mitochondrial rhomboids form an evolutionarily distinct class of rhomboids. It is largely unclear how their activity is controlled and which substrate determinants are responsible for recognition and cleavage. We investigated these requirements for the mitochondrial rhomboid protease Pcp1 and its substrate Mgm1. In contrast to several other rhomboid proteases, Pcp1 does not require helix-breaking amino acids in the cleaved hydrophobic region of Mgm1, termed 'rhomboid cleavage region' (RCR). Even transmembrane segments of inner membrane proteins that are normally not processed by Pcp1 become cleavable when put in place of the authentic RCR of Mgm1. We further show that mutational alterations of a highly negatively charged region located C-terminally to the RCR led to a strong processing defect. Moreover, we show that the determinants required for Mgm1 processing by mitochondrial rhomboid protease are conserved during evolution, as PARL (the human ortholog of Pcp1) showed similar substrate requirements. These results suggest a surprising promiscuity of the mitochondrial rhomboid protease regarding the sequence requirements of the cleaved hydrophobic segment. We propose a working hypothesis on how the mitochondrial rhomboid protease can, despite this promiscuity, achieve a high specificity in recognizing Mgm1. This hypothesis relates to the exceptional biogenesis pathway of Mgm1.