Neurophysiologic correlates of motor learning that can be monitored during neurorehabilitation interventions can facilitate the development of more effective learning methods. Previous studies have focused on the role of the beta band (14–30 Hz) because of its clear response during motor activity. However, it is difficult to discriminate between beta activity related to learning a movement and performing the movement. In this study, we analysed differences in the electroencephalography (EEG) power spectra of complex and simple explicit sequential motor tasks in healthy young subjects. The complex motor task (CMT) allowed EEG measurement related to motor learning. In contrast, the simple motor task (SMT) made it possible to control for EEG activity associated with performing the movement without significant motor learning. Source reconstruction of the EEG revealed task-related activity from 5 clusters covering both primary motor cortices (M1) and 3 clusters localised to different parts of the cingulate cortex (CC). We found no association between M1 beta power and learning, but the CMT produced stronger bilateral beta suppression compared to the SMT. However, there was a positive association between contralateral M1 theta (5–8 Hz) and alpha (8–12 Hz) power and motor learning, and theta and alpha power in the posterior mid-CC and posterior CC were positively associated with greater motor learning. These findings suggest that the theta and alpha bands are more related to motor learning than the beta band, which might merely relate to the level of perceived difficulty during learning.