Motor learning can improve movement performance and behavioral measurements, such as reaction time, by inducing brain plasticity. In this study, we investigated the effect of training with different task complexity on Electroencephalographic (EEG) signals. Two types of training (‘simple’ and ‘complex’) were performed by two groups of healthy volunteers. The complex training group (CTG) performed a trace tracking task using their dominant foot and the simple training group (STG) executed repetitive ankle dorsiflexion in the training phase. Frequency analysis was performed to study the effect of training on EEG signals. In addition, the coherence between paired-channels investigated to represent changes in brain region connectivity. Results revealed that the power in the Beta (15−31 Hz) was significantly reduced while gamma band power (32−80 Hz) was significantly enhanced in the CTG compared to the STG mainly in the frontal, central and centro-parietal channels. Theta power was also increased after training in fronto-central channel. Moreover, performance variations were mainly correlated to the beta and gamma power changes. Finally, the connectivity of gamma and beta band increased significantly particularly between frontal and central region in CTG while connectivity score of theta and delta band decreased after training. These findings confirm that training-induced brain plasticity depends on the complexity of the task, more complexity.