Cytochrome c oxidase (COX) deficiency has been associated with a variety of clinical conditions and can be due to mutations in nuclear or mitochondrial genes. Despite recent progress in our understanding of the molecular bases of COX deficiency, the genetic defect remains elusive in many cases. We performed mutation screening in 30 patients with biochemical evidence of isolated COX deficiency and heterogeneous clinical phenotypes. Sixteen patients had various forms of encephalomyopathy, and six of these had the neuroradiological features of Leigh syndrome. Four patients had encephalohepatopathy, six had hypertrophic cardiomyopathy, and four had other phenotypes. We studied the three mtDNA genes encoding COX subunits, the 22 mtDNA tRNA genes, and seven COX assembly genes: SCO1, SCO2, SURF1, COX10, COX11, COX15, and COX17. We report two novel pathogenic SURF1 mutations in a patient with Leigh syndrome and one novel SCO2 mutation in a patient with hypertrophic cardiomyopathy. These data show that heterogeneous clinical phenotypes are associated with COX deficiency, that mutations in mtDNA COX genes are rare, and that mutations in additional genes remain to be identified.