Abstract Background Mitochondria are highly complex, membrane-enclosed organelles that are essential to the eukaryotic cell. The experimental elucidation of organellar proteomes combined with the sequencing of complete genomes allows us to trace the evolution of the mitochondrial proteome. Results We present a systematic analysis of the evolution of mitochondria via gene duplication in the human lineage. The most common duplications are intra-mitochondrial, in which the ancestral gene and the daughter genes encode mitochondrial proteins. These duplications significantly expanded carbohydrate metabolism, the protein import machinery and the calcium regulation of mitochondrial activity. The second most prevalent duplication, inter-compartmental, extended the catalytic as well as the RNA processing repertoire by the novel mitochondrial localization of the protein encoded by one of the daughter genes. Evaluation of the phylogenetic distribution of N-terminal targeting signals suggests a prompt gain of the novel localization after inter-compartmental duplication. Relocalized duplicates are more often expressed in a tissue-specific manner relative to intra-mitochondrial duplicates and mitochondrial proteins in general. In a number of cases, inter-compartmental duplications can be observed in parallel in yeast and human lineages leading to the convergent evolution of subcellular compartments. Conclusions One-to-one human-yeast orthologs are typically restricted to their ancestral subcellular localization. Gene duplication relaxes this constraint on the cellular location, allowing nascent proteins to be relocalized to other compartments. We estimate that the mitochondrial proteome expanded at least 50% since the common ancestor of human and yeast.