Complex motor behaviors involve the precise coordination of different body parts. While motor coordination has been extensively studied in expert animals, the behavioral and neural processes involved in its emergence through learning are still not well understood. To answer this question, we combined longitudinal behavioral analyses with population recordings from the cerebellum, which is a key region for movement coordination and motor learning. We trained mice to walk on a motorized runged treadmill over multiple days while Ca2+-activity was recorded from cerebellar molecular layer interneurons (MLIs). Motorization and rungs obliged mice to walk slower and with different stride lengths than in their natural gait. High-speed behavioral video recordings allowed us to extract paw trajectories and to assess how mice learned to control stepping patterns in this novel task that required coordination both between limbs, and the coordination of single limbs with the runged treadmill. Over learning, mice acquired a novel gait pattern (diagonal sequence walk) not typically used for locomotion. We found that across animals, fixed pairwise swing-stance phase differences between limbs emerge over days. Using a neural population decoder, we show that cerebellar MLIs encode pairwise phase differences of limbs. We finally asked whether fixed pairwise phase relationships emerge through stronger interlimb coupling or rather by an increase in regularity of single-paw stepping patterns. To address these possibilities, we fit paw position dynamics to a coupled oscillator model in which intrinsic frequencies change stochastically according to a Hidden Markov Model (HMM). With this model we find that over learning, mice adjust single-limb stepping frequencies so that fixed-point dynamics in interlimb coordination become possible.