Background: While decreased alpha and beta-band functional connectivity (FC) and changes in network topology have been reported in Alzheimer’s disease, it is not yet entirely known whether these differences can mark cognitive decline in the early stages of the disease. Our study aimed to analyze electroencephalography (EEG) FC and network differences in the alpha and beta frequency band during visuospatial memory maintenance between Mild Cognitive Impairment (MCI) patients and healthy elderly with subjective memory complaints. Methods: Functional connectivity and network structure of 17 MCI patients and 20 control participants were studied with 128-channel EEG during a visuospatial memory task with varying memory load. FC between EEG channels was measured by amplitude envelope correlation with leakage correction (AEC-c), while network analysis was performed by applying the Minimum Spanning Tree (MST) approach, which reconstructs the critical backbone of the original network. Results: Memory load (increasing number of to-be-learned items) enhanced the mean AEC-c in the control group in both frequency bands. In contrast to that, after an initial increase, the MCI group showed significantly (p < 0.05) diminished FC in the alpha band in the highest memory load condition, while in the beta band this modulation was absent. Moreover, mean alpha and beta AEC-c correlated significantly with the size of medial temporal lobe structures in the entire sample. The network analysis revealed increased maximum degree, betweenness centrality, and degree divergence, and decreased diameter and eccentricity in the MCI group compared to the control group in both frequency bands independently of the memory load. This suggests a rerouted network in the MCI group with a more centralized topology and a more unequal traffic load distribution. Conclusion: Alpha- and beta-band FC measured by AEC-c correlates with cognitive load-related modulation, with subtle medial temporal lobe atrophy, and with the disruption of hippocampal fiber integrity in the earliest stages of cognitive decline. The more integrated network topology of the MCI group is in line with the “hub overload and failure” framework and might be part of a compensatory mechanism or a consequence of neural disinhibition.