Chronic fatigue syndrome (CFS) is a chronic and extremely debilitating illness characterized by prolonged fatigue and multiple symptoms with unknown cause, diagnostic test, or universally effective treatment. Inflammation, oxidative stress, mitochondrial dysfunction, and CoQ10 deficiency have been well documented in CFS. We conducted an 8-week, randomized, double-blind placebo-controlled trial to evaluate the benefits of oral CoQ10 (200 mg/day) plus NADH (20 mg/day) supplementation on fatigue and biochemical parameters in 73 Spanish CFS patients. This study was registered in ClinicalTrials.gov (NCT02063126). A significant improvement of fatigue showing a reduction in fatigue impact scale total score (p<0.05) was reported in treated group versus placebo. In addition, a recovery of the biochemical parameters was also reported. NAD+/NADH (p<0.001), CoQ10 (p<0.05), ATP (p<0.05), and citrate synthase (p<0.05) were significantly higher, and lipoperoxides (p<0.05) were significantly lower in blood mononuclear cells of the treated group. These observations lead to the hypothesis that the oral CoQ10 plus NADH supplementation could confer potential therapeutic benefits on fatigue and biochemical parameters in CFS. Larger sample trials are warranted to confirm these findings.