Most mitochondrial proteins contain an N-terminal targeting signal that is removed by specific proteases following import. In plant mitochondria, only mitochondrial processing peptidase (MPP) has been characterized to date. Therefore, we sought to determine the substrates and cleavage sites of the Arabidopsis thaliana homologues to the yeast Icp55 and Oct1 proteins, using the newly developed ChaFRADIC method for N-terminal protein sequencing. We identified 88 and seven putative substrates for Arabidopsis ICP55 and OCT1, respectively. It was determined that the Arabidopsis ICP55 contains an almost identical cleavage site to that of Icp55 from yeast. However, it can also remove a far greater range of amino acids. The OCT1 substrates from Arabidopsis displayed no consensus cleavage motif, and do not contain the classical –10R motif identified in other eukaryotes. Arabidopsis OCT1 can also cleave presequences independently, without the prior cleavage of MPP. It was concluded that while both OCT1 and ICP55 were probably acquired early on in the evolution of mitochondria, their substrate profiles and cleavage sites have either remained very similar or diverged completely.