Background: An analysis of cortical activity by electroencephalogram (EEG) may show different patterns in depressed and normal individuals. Objectives: Our study aimed (1) to compare the total mean frequency (TMF) and mean EEG frequency per bands (MFB) in depressed and healthy elderly individuals, and (2) to verify the effect of exercise as an additional treatment for major depressive disorder (MDD; according to DSM-IV) via an assessment of depressive symptoms, TMF and MFB. Methods: This research was divided into 2 studies. In study 1, we assessed 45 elderly individuals (13 normal and 32 depressive) in a cross-sectional design to search for differences in TMF and MFB. In study 2, we conducted a longitudinal study to assess the effect of exercise on MDD. Twenty depressed elderly persons who were on clinical treatment were allocated to a control group or an exercise group. Subjects were assessed at baseline and after 6 months with the Hamilton Depression Rating Scale, also assessing the TMF and MFB. Results: Our cross-sectional study showed that a lower mean frequency (MF) in posterior areas is related to depression in the elderly. Moreover, in our longitudinal study, we observed that depressed elderly individuals showed a better response to treatment and an increase in MF after physical training. Conclusion: The interaction between exercise and pharmacological treatment may increase the TMF in posterior areas of depressed elderly individuals after 6 months.