As with other mitochondrial respiratory chain components, marked clinical and genetic heterogeneity is observed in patients with a cytochrome c oxidase deficiency. This constitutes a considerable diagnostic challenge and raises a number of puzzling questions. So far, pathological mutations have been reported in more than 30 genes, in both mitochondrial and nuclear DNA, affecting either structural subunits of the enzyme or proteins involved in its biogenesis. In this review, we discuss the possible causes of the discrepancy between the spectacular advances made in the identification of the molecular bases of cytochrome oxidase deficiency and the lack of any efficient treatment in diseases resulting from such deficiencies. This brings back many unsolved questions related to the frequent delay of clinical manifestation, variable course and severity, and tissue-involvement often associated with these diseases. In this context, we stress the importance of studying different models of these diseases, but also discuss the limitations encountered in most available disease models. In the future, with the possible exception of replacement therapy using genes, cells or organs, a better understanding of underlying mechanism(s) of these mitochondrial diseases is presumably required to develop efficient therapy.