A protein's function is intimately linked to its correct subcellular location, yet the machinery required for protein synthesis is predominately cytosolic. How proteins are trafficked through the confines of the cell and integrated into the appropriate cellular compartments has puzzled and intrigued researchers for decades. Indeed, studies exploring this premise revealed elaborate cellular protein translocation and sorting systems, which ensure that all proteins are shuttled to the appropriate cellular destination, where they fulfill their specific functions. This holds true for mitochondria, where sophisticated molecular machines serve to recognize incoming precursor proteins and integrate them into the functional framework of the organelle. We summarize the recent progress in our understanding of mitochondrial protein sorting and the machineries and mechanisms that mediate and regulate this highly dynamic cellular process essential for survival of virtually all eukaryotic cells.