Mitochondria are eukaryotic organelles originated from a single bacterial endosymbiosis about 2 billion years ago. One of the earliest events in the evolution of mitochondria was the acquisition of a mechanism that facilitated the import of proteins from cytosol. The mitochondrial protein import machinery consists of dozens of subunits, and they are of modular design. However, to date, it is not clear when certain component was added to the machinery. Using extensive homology searches, the evolutionary history of the mitochondrial protein import machinery was reconstructed. The results indicated that 6 of the 35 subunits have homologs in prokaryote, suggesting that they were prokaryotic origin; the major subunit gains were occurred in the earliest stage of eukaryotic evolution; subsequent to the gain of these conserved set of subunits, the mitochondrial protein import machinery components diversified along the eukaryotic lineages and a number of lineage-specific subunits can be observed. Furthermore, protein import systems of mitochondria-like organelles (hydrogenosomes and mitosomes) have dramatically reduced their subunit contents, however, they share most of the prokaryotic origin components with mitochondrion.