Restorer-of-fertility (Rf) genes encode pentatricopeptide repeat (PPR) proteins that are targeted to mitochondria where they specifically bind to transcripts that induce cytoplasmic male sterility and repress their expression. In searching for a molecular signature unique to this class of proteins, we found that a majority of known Rf proteins have a distinct domain, which we called RfCTD (Restorer-of-fertility C-terminal domain), and its presence correlates with the ability to induce cleavage of the mitochondrial RNA target. A screen of 219 angiosperm genomes from 123 genera using a sequence profile that can quickly and accurately identify RfCTD sequences revealed considerable variation in RFL/RfCTD gene numbers across flowering plants. We observed that plant genera with bisexual flowers have significantly higher numbers of RFL genes compared to those with unisexual flowers, consistent with a role of these proteins in restoration of male fertility. We show that removing the RfCTD from the RFL protein RNA PROCESSING FACTOR 2-nad6 prevented cleavage of its RNA target, the nad6 transcript, in Arabidopsis thaliana mitochondria. We provide a simple way of identifying putative Rf candidates in genome sequences, new insights into the molecular mode of action of Rf proteins and the evolution of fertility restoration in flowering plants.