Body and brain undergo several changes with aging. One of the domains in which these changes are more remarkable relates with cognitive performance. In the present work, electroencephalogram (EEG) markers (power spectral density and spectral coherence) of age-related cognitive decline were sought whilst the subjects performed the Wisconsin Card Sorting Test (WCST). Considering the expected age-related cognitive deficits, WCST was applied to young, mid-age and elderly participants, and the theta and alpha frequency bands were analyzed. From the results herein presented, higher theta and alpha power were found to be associated with a good performance in the WCST of younger subjects. Additionally, higher theta and alpha coherence were also associated with good performance and were shown to decline with age and a decrease in alpha peak frequency seems to be associated with aging. Additionally, inter-hemispheric long-range coherences and parietal theta power were identified as age-independent EEG correlates of cognitive performance. In summary, these data reveals age-dependent as well as age-independent EEG correlates of cognitive performance that contribute to the understanding of brain aging and related cognitive deficits.