Whole-body movements like locomotion require timely and precise coordination of multiple effectors. Moreover, control needs to be robust and flexible to changes in the state of the body and environment. How is such a complex control problem solved by the brain? The cerebellum is critical for coordinating movement; during locomotion it is particularly important for interlimb and whole-body coordination. Decades of recordings have consistently shown that Purkinje cell modulation (the sole output of the cerebellar cortex) is broadly correlated with the locomotor stride cycle. However, much of the firing rate variability has remained unexplained; moreover, previous analyses do not provide a clear model for how Purkinje cell activity could be read out to control coordination. Here we performed cell-attached recordings from individual Purkinje cells in head-fixed mice during locomotion, along with continuous, high-speed tracking of limb and body kinematics. We find that beyond representing the locomotor stride cycle, Purkinje cells are exquisitely sensitive to stride-to-stride kinematic variation. Further, analyzing responses with respect to movements across the body reveals that many individual Purkinje cells respond to multiple behavioral events, including movements of multiple limbs. To disentangle the contribution of individual limbs in light of the high degree of correlation imposed by the locomotor pattern, we used Generalized Additive Models (GAMs). GAMs allow us to simultaneously approximate even highly non-linear contributions of multiple body parts to the overall activity of individual neurons. This modeling reveals that a substantial proportion of Purkinje cells simultaneously encode movements of multiple limbs and body parts to provide precise representations of temporal coordination across diverse combinations of behavioral events. High prevalence of this non-linear mixed selectivity across the Purkinje cell population resolves long-standing controversies surrounding the role of Purkinje cells in locomotor control and could allow for efficient readouts of whole-body coordination by a simple linear decoder.