A fundamental question in neuroscience is how entire neural circuits generate behaviour and adapt it to changes in sensory feedback. Here we use two-photon calcium imaging to record the activity of large populations of neurons at the cellular level, throughout the brain of larval zebrafish expressing a genetically encoded calcium sensor, while the paralysed animals interact fictively with a virtual environment and rapidly adapt their motor output to changes in visual feedback. We decompose the network dynamics involved in adaptive locomotion into four types of neuronal response properties, and provide anatomical maps of the corresponding sites. A subset of these signals occurred during behavioural adjustments and are candidates for the functional elements that drive motor learning. Lesions to the inferior olive indicate a specific functional role for olivocerebellar circuitry in adaptive locomotion. This study enables the analysis of brain-wide dynamics at single-cell resolution during behaviour.