Although recent evidence has demonstrated the potent effect of physical exercise to increase the efficacy of cognitive training, the neural mechanisms underlying this causal relationship remain unclear. Here, we used multiscale entropy (MSE) of electroencephalography (EEG)—a measure of brain signal complexity—to address this issue. Young males were randomly assigned to either a 20-day dual n-back training following aerobic exercise or the same training regimen following a reading. A feature binding working memory task with concurrent EEG recording was used to test for transfer effects. Although results revealed weak-to-moderate evidence for exercise-induced facilitation on cognitive training, the combination of cognitive training with exercise resulted in greater transfer gains on conditions involving greater attentional demanding, together with greater increases in cognitive modulation on MSE, compared with the reading condition. Overall, our findings suggest that the addition of antecedent physical exercise to brain training regimen could enable wider, more robust improvements.