The cerebellum is critical for coordinating movement, and during locomotion it is particularly important for interlimb coordination. Decades of recordings have consistently shown that cerebellar Purkinje cell modulation is broadly correlated with the locomotor stride cycle. However, much of the firing rate variability has remained unexplained, and it is not yet clear how Purkinje cell population activity could be read out to control whole-body coordination. Here, we performed cell-attached recordings of Purkinje cell simple spike activity in head-fixed mice locomoting for liquid rewards, together with high-speed 3D tracking of body kinematics, and quantified the contributions of specific behavioral features to overall firing rate using Generalized Additive Models. Our analyses reveal that beyond representing the locomotor stride cycle, Purkinje cells are exquisitely sensitive to stride-to-stride kinematic variation. Further, the vast majority of Purkinje cells simultaneously encode movements of multiple body parts to provide precise representations of temporal coordination across the body. Together, these findings resolve much of the long-standing confusion surrounding the role of Purkinje cells in locomotor control. Finally, we found that simple spike activity in most locomotion-modulated Purkinje cells exhibits non-linear sensitivity to interactions of the movements of multiple limbs. Preliminary simulation results suggest that the high prevalence of non-linear mixed selectivity across the Purkinje cell population could allow for efficient readouts of locomotor coordination by a simple linear decoder, explaining how the cerebellum flexibly coordinates interlimb and whole-body movements in dynamic environments.