It is estimated that the human mitochondrial proteome consists of 1000-1500 distinct proteins. The majority of these support the various biochemical pathways that are active in these organelles. Individuals with an oxidative phosphorylation disorder of unknown cause provide a unique opportunity to identify novel genes implicated in mitochondrial biology. We identified a homozygous deletion of CEP89 in a patient with isolated complex IV deficiency, intellectual disability and multisystemic problems. CEP89 is a ubiquitously expressed and highly conserved gene of unknown function. Immunocytochemistry and cellular fractionation experiments showed that CEP89 is present both in the cytosol and in the mitochondrial intermembrane space. Furthermore, we ascertained in vitro that downregulation of CEP89 resulted in a severe decrease in complex IV in-gel activity and altered mobility, suggesting that the complex is aberrantly formed. Two-dimensional BN-SDS gel analysis revealed that CEP89 associates with a high-molecular weight complex. Together, these data confirm a role for CEP89 in mitochondrial metabolism. In addition, we modeled CEP89 loss of function in Drosophila. Ubiquitous knockdown of fly Cep89 decreased complex IV activity and resulted in complete lethality. Furthermore, Cep89 is required for mitochondrial integrity, membrane depolarization and synaptic transmission of photoreceptor neurons, and for (sub)synaptic organization of the larval neuromuscular junction. Finally, we tested neuronal Cep89 knockdown flies in the light-off jump reflex habituation assay, which revealed its role in learning. We conclude that CEP89 proteins play an important role in mitochondrial metabolism, especially complex IV activity, and are required for neuronal and cognitive function across evolution.