Locomotion involves the precise coordination of different body parts. On structured surfaces, animals additionally have to adapt their gait to properties of the environment. To study the dynamical principles of locomotor learning in novel environments, we trained mice to walk on a motorized treadmill with evenly spaced rungs. We extracted paw trajectories from behavioral videos and analyzed stepping patterns over the course of two weeks of learning. In early sessions, mouse gaits were highly irregular, with variable inter-paw coordination. Over sessions, coordination between paws increased, leading to fixed pairwise phase differences in the swing-stance cycle. To understand how stable coordination emerged from highly irregular gaits, we modeled gait dynamics by fitting coupled-oscillator models to the behavioral time series. The introduction of switching dynamical regimes and Gaussian process coupling functions allowed us to extract lawful dynamics in early as well as late sessions, despite frequent adjustments of stepping patterns to the runged surface. With this approach, we find that coordinated locomotion on complex surfaces depends on a dual learning process: On the one hand, mice learned to use advantageous, naturalistic stepping patterns more extensively; on the other hand, dynamic entrainment between paws increased, leading to efficient, fine-grained coordination between paws.