Chronic progressive external ophthalmoplegia (CPEO) is a common presentation of mitochondrial disease. We performed a retrospective evaluation of the molecular genetic testing and genotype-phenotype correlations in a large cohort of adult-onset CPEO patients (N = 111). One hundred percent of patients tested had at least one mitochondrial DNA (mtDNA) deletion. Genetic testing of nuclear genes encoding mitochondrial proteins identified pathogenic/likely pathogenic variants likely to be associated with CPEO in 7.6% of patients. As expected, the nuclear gene most associated with DNA variation was POLG. A single likely pathogenic mitochondrial DNA variant (m.12278T>C) was identified in two unrelated patients. No significant differences were noted in the clinical phenotypes of patients with pathogenic or likely pathogenic nuclear variants in comparison to those with negative nuclear gene testing. Analysis of deletion size and heteroplasmy in muscle-derived mtDNA showed significant correlations with age of symptom onset but not disease severity (number of canonical CPEO features). Results suggest that smaller mtDNA deletions (p = 0.0127, r = 0.1201) and higher heteroplasmy of single mtDNA deletions (p = 0.0112, r = 0.2483) are associated with an earlier age of onset in CPEO patients.