Recent findings have demonstrated that stroke lesions affect neural communication in the entire brain. However, it is less clear whether network interactions are also relevant for plasticity and repair. This study investigated whether the coherence of neural oscillations at language or motor nodes is associated with future clinical improvement. Twenty-four stroke patients underwent high-density EEG recordings and standardized motor and language tests at 2-3 weeks (T0) and 3 months (T1) after stroke onset. In addition, EEG and motor assessments were obtained from a second population of 18 stroke patients. The graph theoretical measure of weighted node degree at language and motor areas was computed as the sum of absolute imaginary coherence with all other brain regions and compared to the amount of clinical improvement from T0 to T1. At T0, beta-band weighted node degree at the ipsilesional motor cortex was linearly correlated with better subsequent motor improvement, while beta-band weighted node degree at Broca's area was correlated with better language improvement. Clinical recovery was further associated with contralesional theta-band weighted node degree. These correlations were each specific to the corresponding brain area and independent of initial clinical severity, age, and lesion size. Findings were reproduced in the second stroke group. Conversely, later coherence increases occurring between T0 and T1 were associated with less clinical improvement. Improvement of language and motor functions after stroke is therefore associated with inter-regional synchronization of neural oscillations in the first weeks after stroke. A better understanding of network mechanisms of plasticity may lead to new prognostic biomarkers and therapeutic targets.