Cognitive impairment, particularly prefrontal function, has been reported in patients with restless legs syndrome. However, working memory performance in patients with restless legs syndrome remains uncertain. The present study aimed to examine working memory performance in patients with restless legs syndrome by investigating electroencephalography theta-band oscillations within task-relevant brain regions and the synchronization among oscillations during a working memory task. Twelve female idiopathic patients with restless legs syndrome and 12 female healthy controls participated in this study. Nineteen-channel electroencephalography data were recorded while participants performed a Sternberg working memory task. We analysed event-related theta-band activity and interregional theta-band phase synchrony during the memory retrieval phase. The spatial pattern of theta-band phase synchrony was quantified using graph theory measures, including the clustering coefficient, characteristic path length, and small-world propensity. Considerable increases in theta-band activity and theta-band phase synchrony were observed at 600–700 ms in controls and at 650–750 ms in restless legs syndrome subjects after the probe item was presented. During this period, induced theta-band activity showed lower with borderline significance in the restless legs syndrome subjects than in the controls regardless of channel location (F4,88 = 3.92, p =.06). Theta-band phase synchrony between the frontal and posterior regions was significantly reduced in the restless legs syndrome subjects. Inefficiency in both global and local networks in the restless legs syndrome subjects was revealed by the decreased small-world propensity (t22 = 2.26, p =.03). Small-world propensity was negatively correlated with restless legs syndrome severity (r = −.65, p =.02). Our findings suggest that patients with restless legs syndrome have multiple deficits in cognitive processes, including attentional allocation, evaluation of incoming stimuli, and memory manipulation of encoded information during a working memory task. Abnormal local theta-band neural synchrony and global theta-band neural synchrony may underlie the neurophysiological mechanism of the working memory dysfunction associated with restless legs syndrome.