Cytochrome c oxidase (COX) or complex IV of the mitochondrial respiratory chain plays a fundamental role in energy production of aerobic cells. In humans, COX deficiency is the most frequent cause of mitochondrial encephalomyopathies. Human COX is composed of 13 subunits of dual genetic origin, whose assembly requires an increasing number of nuclear-encoded accessory proteins known as assembly factors. Here, we have identified and characterized human CCDC56, an 11.7-kDa mitochondrial transmembrane protein, as a new factor essential for COX biogenesis. CCDC56 shares sequence similarity with the yeast COX assembly factor Coa3 and was termed hCOA3. hCOA3-silenced cells display a severe COX functional alteration owing to a decreased stability of newly synthesized COX1 and an impairment in the holoenzyme assembly process. We show that hCOA3 physically interacts with both the mitochondrial translation machinery and COX structural subunits. We conclude that hCOA3 stabilizes COX1 co-translationally and promotes its assembly with COX partner subunits. Finally, our results identify hCOA3 as a new candidate when screening for genes responsible for mitochondrial diseases associated with COX deficiency.