All eukaryotes require mitochondria for survival and growth. The origin of mitochondria can be traced down to a single endosymbiotic event between two probably prokaryotic organisms. Subsequent evolution has left mitochondria a collection of heterogeneous organelle variants. Most of these variants have retained their own genome and translation system. In hydrogenosomes and mitosomes, however, the entire genome was lost. All types of mitochondria import most of their proteome from the cytosol, irrespective of whether they have a genome or not. Moreover, in most eukaryotes, a variable number of tRNAs that are required for mitochondrial translation are also imported. Thus, import of macromolecules, both proteins and tRNA, is essential for mitochondrial biogenesis. Here, we review what is known about the evolutionary history of the two processes using a recently revised eukaryotic phylogeny as a framework. We discuss how the processes of protein import and tRNA import relate to each other in an evolutionary context.