Cytochrome c oxidase (COX) deficiency is characterized by a high degree of genetic and phenotypic heterogeneity, partly reflecting the extreme structural complexity, multiple post-translational modification, variable, tissue-specific composition, and the high number of and intricate connections among the assembly factors of this enzyme. In fact, decreased COX specific activity can manifest with different degrees of severity, affect the whole organism or specific tissues, and develop a wide spectrum of disease natural history, including disease onsets ranging from birth to late adulthood. More than 30 genes have been linked to COX deficiency, but the list is still incomplete and in fact constantly updated. We here discuss the current knowledge about COX in health and disease, focusing on genetic aetiology and link to clinical manifestations. In addition, information concerning either fundamental biological features of the enzymes or biochemical signatures of its defects have been provided by experimental in vivo models, including yeast, fly, mouse and fish, which expanded our knowledge on the functional features and the phenotypical consequences of different forms of COX deficiency.