Deep brain stimulation (DBS) of the subthalamic nucleus (STN) is an established symptomatic treatment in Parkinson's disease, yet its mechanism of action is not fully understood. Locally in the STN, stimulation lowers beta band power, in parallel with symptom relief. Therefore, beta band oscillations are sometimes referred to as “anti-kinetic”. However, in recent studies functional interactions have been observed beyond the STN, which we hypothesized to reflect clinical effects of DBS. Resting-state, whole-brain magnetoencephalography (MEG) recordings and assessments on motor function were obtained in 18 Parkinson's disease patients with bilateral STN-DBS, on and off stimulation. For each brain region, we estimated source-space spectral power and functional connectivity with the rest of the brain. Stimulation led to an increase in average peak frequency and a suppression of absolute band power (delta to low-beta band) in the sensorimotor cortices. Significant changes (decreases and increases) in low-beta band functional connectivity were observed upon stimulation. Improvement in bradykinesia/rigidity was significantly related to increases in alpha2 and low-beta band functional connectivity (of sensorimotor regions, the cortex as a whole, and subcortical regions). By contrast, tremor improvement did not correlate with changes in functional connectivity. Our results highlight the distributed effects of DBS on the resting-state brain and suggest that DBS-related improvements in rigidity and bradykinesia, but not tremor, may be mediated by an increase in alpha2 and low-beta functional connectivity. Beyond the local effects of DBS in and around the STN, functional connectivity changes in these frequency bands might therefore be considered as “pro-kinetic”.