Background: Stroke is the second leading cause of death worldwide and it causes important long-term cognitive and physical deficits that hamper patients' daily activity. Neuropsychological rehabilitation (NR) has increasingly become more important to recover from cognitive disability and to improve the functionality and quality of life of these patients. Since in most stroke cases, restoration of functional connectivity (FC) precedes or accompanies cognitive and behavioral recovery, understanding the electrophysiological signatures underlying stroke recovery mechanisms is a crucial scientific and clinical goal. Methods: For this purpose, a longitudinal study was carried out with a sample of 10 stroke patients, who underwent two neuropsychological assessments and two resting-state magnetoencephalographic (MEG) recordings, before and after undergoing a NR program. Moreover, to understand the degree of cognitive and neurophysiological impairment after stroke and the mechanisms of recovery after cognitive rehabilitation, stroke patients were compared to 10 healthy controls matched for age, sex, and educational level. Findings: After intra and inter group comparisons, we found the following results: (1) Within the stroke group who received cognitive rehabilitation, almost all cognitive domains improved relatively or totally; (2) They exhibit a pattern of widespread increased in FC within the beta band that was related to the recovery process (there were no significant differences between patients who underwent rehabilitation and controls); (3) These FC recovery changes were related with the enhanced of cognitive performance. Furthermore, we explored the capacity of the neuropsychological scores before rehabilitation, to predict the FC changes in the brain network. Significant correlations were found in global indexes from the WAIS-III: Performance IQ (PIQ) and Perceptual Organization index (POI) (i.e., Picture Completion, Matrix Reasoning, and Block Design).