A single bout of cardiovascular exercise performed immediately after practicing a visuo-motor tracking task has been shown to improve the long-term retention of this motor skill through an optimization of the memory consolidation process. The mechanisms underlying the time-dependent effects of acute cardiovascular exercise on motor memory consolidation, however, remain poorly understood. In this study, we sought to determine the impact of a single bout of cardiovascular exercise performed immediately after motor skill practice on those mechanisms using electroencephalography (EEG) and electromyography (EMG). Specifically, we assessed exercise-induced changes in the activity and connectivity of cortico-motor networks during early consolidation and the impact of these changes on skill retention. Participants practiced a visuo-motor tracking task followed by either a short bout of intense exercise or a rest period. EEG along with EMG data of hand muscles were collected during the production of low-force isometric contractions. Event-related desynchronization, functional connectivity and corticomuscular coherence were measured at baseline, 30, 60 and 90min after the bout of exercise or the rest period. Improvements in motor memory were inferred via retention tests of the motor skill performed 8 and 24h after motor practice. We found that participants who performed the single bout of exercise showed better motor skill retention 24h after motor practice. This improvement in skill retention in the exercise group was associated with significant decreases in beta-band event-related desynchronization in EEG electrodes located over the left sensorimotor areas. We also found that after exercise, alpha-, and even more significantly, beta-band functional connectivity, increased between EEG electrodes located over left and right sensorimotor areas. The exercise group also showed greater beta-band corticomuscular coherence but only in a small number of electrodes. Neither functional connectivity nor corticomuscular coherence measures correlated with skill retention scores. This is the first study exploring brain mechanisms underlying the summative effects of motor learning and cardiovascular exercise on motor memory consolidation. We have identified potential neural substrates through which a single bout of acute exercise, when performed in close temporal proximity to motor practice, strengthens motor memories. Our findings provide new mechanistic insights into a better understanding of the complex temporal relationship existing between cardiovascular exercise and motor memory consolidation.