Advances in next-generation sequencing (NGS) promise to facilitate diagnosis of inherited disorders. Although in research settings NGS has pinpointed causal alleles using segregation in large families, the key challenge for clinical diagnosis is application to single individuals. To explore its diagnostic use, we performed targeted NGS in 42 unrelated infants with clinical and biochemical evidence of mitochondrial oxidative phosphorylation disease. These devastating mitochondrial disorders are characterized by phenotypic and genetic heterogeneity, with more than 100 causal genes identified to date. We performed "MitoExome" sequencing of the mitochondrial DNA (mtDNA) and exons of ~1000 nuclear genes encoding mitochondrial proteins and prioritized rare mutations predicted to disrupt function. Because patients and healthy control individuals harbored a comparable number of such heterozygous alleles, we could not prioritize dominant-acting genes. However, patients showed a fivefold enrichment of genes with two such mutations that could underlie recessive disease. In total, 23 of 42 (55%) patients harbored such recessive genes or pathogenic mtDNA variants. Firm diagnoses were enabled in 10 patients (24%) who had mutations in genes previously linked to disease. Thirteen patients (31%) had mutations in nuclear genes not previously linked to disease. The pathogenicity of two such genes, NDUFB3 and AGK, was supported by complementation studies and evidence from multiple patients, respectively. The results underscore the potential and challenges of deploying NGS in clinical settings.