Muscle dysfunction in mitochondrial myopathy is predominantly caused by insufficient generation of energy. We hypothesise that structural changes in muscles could also contribute to their pathophysiology. The aims of this study were to determine fat fractions and strength in selected muscles in patients with chronic progressive external ophthalmoplegia (CPEO), and compare progression of muscle fat fraction with age in individuals with CPEO vs. healthy controls and patients with the m.3243A>G mutation of mitochondrial DNA (mtDNA). Seventeen patients with CPEO and single large-scale deletions of mtDNA, 52 healthy controls, and 12 patients carrying the m.3243A>G mtDNA mutation were included. Muscle fat fractions were measured from cross-sections of paraspinal and leg muscles. Peak muscle strength was assessed from a static dynamometer. There was a direct correlation between age and fat fraction in all muscle groups in CPEO patients and healthy controls (p < 0.05). Analysis of covariance showed a higher progression rate of fat replacement in CPEO patients vs. healthy controls in studied muscle groups (p < 0.05). Patients with the m.3243A>G mutation had slower progression rates of fat replacement. Muscle strength decreased with increasing muscular fat fraction in CPEO patients, no correlation was seen in other groups. This indicates that structural muscle changes contribute to the phenotype of older patients affected by CPEO and large-scale deletions. It should therefore be considered, along with known energy deficiencies, as the cause of exercise intolerance.