Mitochondrial protein import is essential for all eukaryotes and mediated by hetero-oligomeric protein translocases thought to be conserved within all eukaryotes. We have identified and analysed the function and architecture of the non-conventional outer membrane (OM) protein translocase in the early diverging eukaryote Trypanosoma brucei. It consists of six subunits that show no obvious homology to translocase components of other species. Two subunits are import receptors that have a unique topology and unique protein domains and thus evolved independently of the prototype receptors Tom20 and Tom70. Our study suggests that protein import receptors were recruited to the core of the OM translocase after the divergence of the major eukaryotic supergroups. Moreover, it links the evolutionary history of mitochondrial protein import receptors to the origin of the eukaryotic supergroups.