Mitochondria evolved from an endosymbiotic proteobacterium in a process that required the transfer of genes from the bacterium to the host cell nucleus, and the translocation of proteins thereby made in the host cell cytosol into the internal compartments of the organelle. According to current models for this evolution, two highly improbable events are required to occur simultaneously: creation of a protein translocation machinery to import proteins back into the endosymbiont and creation of targeting sequences on the protein substrates themselves. Using a combination of two independent prediction methods, validated through tests on simulated genomes, we show that at least 5% of proteins encoded by an extant proteobacterium are predisposed for targeting to mitochondria, and propose we that mitochondrial targeting information was preexisting for many proteins of the endosymbiont. We analyzed a family of proteins whose members exist both in bacteria and in mitochondria of eukaryotes and show that the amino-terminal extensions occasionally found in bacterial family members can function as a crude import sequence when the protein is presented to isolated mitochondria. This activity leaves the development of a primitive translocation channel in the outer membrane of the endosymbiont as a single hurdle to initiating the evolution of mitochondria.