Complex I deficiency is the most frequent mitochondrial disorder presenting in childhood, accounting for up to 30% of cases. As with many mitochondrial disorders, complex I deficiency is characterised by marked clinical and genetic heterogeneity, leading to considerable diagnostic challenges for the clinician, not least because of the involvement of two genomes. The most prevalent clinical presentations include Leigh syndrome, leukoencephalopathy and other early-onset neurodegenerative disorders; fatal infantile lactic acidosis; hypertrophic cardiomyopathy; and exercise intolerance. Causative genetic defects may involve the seven mitochondrial-encoded or 38 nuclear-encoded subunits of the enzyme, or any of an increasing number of assembly factors implicated in the correct biosynthesis of complex I within the inner mitochondrial membrane. In this review, we discuss recent advances in knowledge of the structure, function and assembly of complex I and how these advances, together with new high-throughput genetic screening techniques, have translated into improved genetic diagnosis for affected patients and their families. Approximately 25% of cases have mitochondrial DNA mutations, while a further ∼25% have mutations in a nuclear subunit or in one of nine known assembly factors. We also present a systematic review of all published cases of nuclear-encoded complex I deficiency, including 117 cases with nuclear subunit mutations and 55 with assembly factor mutations, and highlight clinical, radiological and biochemical clues that may expedite genetic diagnosis.