In recent years, mounting evidence from animal models and studies in humans has accumulated for the role of cardiovascular exercise (CE) in improving motor performance and learning. Both CE and motor learning may induce highly dynamic structural and functional brain changes, but how both processes interact to boost learning is presently unclear. Here, we hypothesized that subjects receiving CE would show a different pattern of learning-related brain plasticity compared to non-CE controls, which in turn associates with improved motor learning. To address this issue, we paired CE and motor learning sequentially in a randomized controlled trial with healthy human participants. Specifically, we compared the effects of a 2-week CE intervention against a non-CE control group on subsequent learning of a challenging dynamic balancing task (DBT) over 6 consecutive weeks. Structural and functional MRI measurements were conducted at regular 2-week time intervals to investigate dynamic brain changes during the experiment. The trajectory of learning-related changes in white matter microstructure beneath parieto-occipital and primary sensorimotor areas of the right hemisphere differed between the CE vs. non-CE groups, and these changes correlated with improved learning of the CE group. While group differences in sensorimotor white matter were already present immediately after CE and persisted during DBT learning, parieto-occipital effects gradually emerged during motor learning. Finally, we found that spontaneous neural activity at rest in gray matter spatially adjacent to white matter findings was also altered, therefore indicating a meaningful link between structural and functional plasticity. Collectively, these findings may lead to a better understanding of the neural mechanisms mediating the CE-learning link within the brain.