The comparison of each of the 393 nuclear-encoded human mitochondrial proteins annotated in the SwissProt databank with 256,953 proteins from 94 prokaryote species showed that two thirds of the mitochondrial proteome were homologous with prokaryotic proteins, whereas one third was not. Prokaryotic mitochondrial proteins differ markedly from eukaryotic proteins, particularly in regard to their size, localization, function, and mitochondrial-targeting N-terminal sequence. Remarkably, the majority of nuclear genes implicated in respiratory chain mitochondrial diseases were found to be of prokaryotic ancestry. Our study indicates that the investigation of the co-evolution of eukaryotic and prokaryotic mitochondrial proteins should lead to a better understanding of mitochondrial diseases.