The formation of the mature cytochrome c oxidase (complex IV) involves the association of nuclear and mitochondria-encoded subunits. The assembly of nuclear-encoded subunits like Cox4 into the mature complex is poorly understood. Cox4 is crucial for the stability of complex IV. To find specific biogenesis factors we analyzed interaction partners of Cox4 by affinity purification and mass spectroscopy. Surprisingly, we identified a complex of Cox4, the mitochondrial Hsp70 (mtHsp70) and its nucleotide-exchange factor Mge1. We generated a yeast mutant of mtHsp70 specifically impaired in the formation of this novel mtHsp70-Mge1-Cox4 complex. Strikingly, the assembly of Cox4 is strongly decreased in these mutant mitochondria. Since Cox4 is a key factor for the biogenesis of complex IV we conclude that the mtHsp70-Mge1-Cox4 complex plays an important role in the formation of cytochrome c oxidase. Cox4 arrests at this chaperone complex in the absence of mature complex IV. Thus, the mtHsp70-Cox4 complex likely serves as a novel delivery system to channel Cox4 into the assembly line when needed.