Physical and cognitive idleness constitute significant risk factors for the clinical manifestation of age-related neurodegenerative diseases. In contrast, a physically and cognitively active lifestyle may restructure age-declined neuronal networks enhancing neuroplasticity. The present study, investigated the changes of brain's functional network in a group of elderly individuals at risk for dementia that were induced by a combined cognitive and physical intervention scheme. Fifty seniors meeting Petersen's criteria of Mild Cognitive Impairment were equally divided into an experimental (LLM), and an active control (AC) group. Resting state electroencephalogram (EEG) was measured before and after the intervention. Functional networks were estimated by computing the magnitude square coherence between the time series of all available cortical sources as computed by standardized low resolution brain electromagnetic tomography (sLORETA). A statistical model was used to form groups' characteristic weighted graphs. The introduced modulation was assessed by networks' density and nodes' strength. Results focused on the beta band (12-30 Hz) in which the difference of the two networks' density is maximum, indicating that the structure of the LLM cortical network changes significantly due to the intervention, in contrast to the network of AC. The node strength of LLM participants in the beta band presents a higher number of bilateral connections in the occipital, parietal, temporal and prefrontal regions after the intervention. Our results show that the combined training scheme reorganizes the beta-band functional connectivity of MCI patients. ClinicalTrials.gov Identifier: NCT02313935 https://clinicaltrials.gov/ct2/show/NCT02313935.