Mitochondrial diseases (MDs) are a group of severe genetic disorders caused by mutations in the nuclear or mitochondrial genome encoding proteins involved in the oxidative phosphorylation (OXPHOS) system. MDs have a wide range of symptoms, ranging from organ-specific to multisystemic dysfunctions, with different clinical outcomes. The lack of natural history information, the limits of currently available preclinical models, and the wide range of phenotypic presentations seen in MD patients have all hampered the development of effective therapies. The growing number of pre-clinical and clinical trials over the last decade has shown that gene therapy is a viable precision medicine option for treating MD. However, several obstacles must be overcome, including vector design, targeted tissue tropism and efficient delivery, transgene expression, and immunotoxicity. This manuscript offers a comprehensive overview of the state of the art of gene therapy in MD, addressing the main challenges, the most feasible solutions, and the future perspectives of the field.