Mitochondria are archetypal organelles of endosymbiotic origin in eukaryotic cells. Some unicellular eukaryotes (protists) were considered to be primarily amitochondrial organisms that diverged from the eukaryotic lineage before the acquisition of the premitochondrial endosymbiont, but their amitochondrial status was recently challenged by the discovery of mitochondria-like double membrane-bound organelles called mitosomes. Here, we report that proteins targeted into mitosomes of Giardia intestinalis have targeting signals necessary and sufficient to be recognized by the mitosomal protein import machinery. Expression of these mitosomal proteins in Trichomonas vaginalis results in targeting to hydrogenosomes, a hydrogen-producing form of mitochondria. We identify, in Giardia and Trichomonas, proteins related to the component of the translocase in the inner membrane from mitochondria and the processing peptidase. A shared mode of protein targeting supports the hypothesis that mitosomes, hydrogenosomes, and mitochondria represent different forms of the same fundamental organelle having evolved under distinct selection pressures.