Objective: Fatigue is a common, debilitating nonmotor symptom of Parkinson’s disease (PD), but its mechanism is poorly understood. We aimed to determine whether electroencephalography (EEG) could objectively measure fatigue and to explore the pathophysiology of fatigue in PD. Methods: We studied 32 de novo PD patients who underwent EEG. We compared brain activity between 19 PD patients without fatigue and 13 PD patients with fatigue via EEG power spectra and graphs, including the global efficiency, characteristic path length, clustering coefficient, small-worldness, local efficiency, degree centrality, closeness centrality, and betweenness centrality. Results: No significant differences in absolute or relative power were detected between PD patients without or with fatigue (all p > 0.02, Bonferroni-corrected). According to our network analysis, brain network efficiency differed by frequency band. Generally, the brain network in the frontal area for theta and delta bands showed greater efficiency, and in the temporal area, the alpha1 band was less efficient in PD patients without fatigue (p < 0.0001, p = 0.0011, and p = 0.0007, respectively, Bonferroni-corrected). Conclusion Our study suggests that PD patients with fatigue have less efficient networks in the frontal area than PD patients without fatigue. These findings may explain why fatigue is common in PD, a frontostriatal disorder. Increased efficiency in the temporal area in PD patients with fatigue is assumed to be compensatory. Brain network analysis using graph theory is more valuable than power spectrum analysis in revealing the brain mechanism related to fatigue.