Cytochrome-c oxidase (COX) deficiency is one of the common childhood mitochondrial disorders. Mutations in genes for the assembly factors SURF1 and SCO2 are prevalent in children with COX deficiency in the Slavonic population. Molecular diagnosis is difficult because of the number of genes involved in COX biogenesis and assembly. The aim of this study was to screen for mutations in 15 nuclear genes that encode the 10 structural subunits, their isoforms and two assembly factors of COX in 60 unrelated Czech children with COX deficiency. Nine novel variants were identified in exons and adjacent intronic regions of COX4I2, COX6A1, COX6A2, COX7A1, COX7A2 and COX10 using high-resolution melting (HRM) analysis. Online bioinformatics servers were used to predict the importance of the newly identified amino-acid substitutions. The newly characterized variants updated the contemporary spectrum of known genetic sequence variations that are present in the Czech population, which will be important for further targeted mutation screening in Czech COX-deficient children. HRM and predictive bioinformatics methodologies are advantageous because they are low-cost screening tools that complement large-scale genomic studies and reduce the required time and effort.