Locomotion is a fundamental motor function common to the animal kingdom. It is implemented episodically and adapted to behavioural needs, including exploration, which requires slow locomotion, and escape behaviour, which necessitates faster speeds. The control of these functions originates in brainstem structures, although the neuronal substrate(s) that support them have not yet been elucidated. Here we show in mice that speed and gait selection are controlled by glutamatergic excitatory neurons (GlutNs) segregated in two distinct midbrain nuclei: the cuneiform nucleus (CnF) and the pedunculopontine nucleus (PPN). GlutNs in both of these regions contribute to the control of slower, alternating-gait locomotion, whereas only GlutNs in the CnF are able to elicit high-speed, synchronous-gait locomotion. Additionally, both the activation dynamics and the input and output connectivity matrices of GlutNs in the PPN and the CnF support explorative and escape locomotion, respectively. Our results identify two regions in the midbrain that act in conjunction to select context-dependent locomotor behaviours. Speed and gait selection in mice are controlled by glutamatergic excitatory neurons in the cuneiform nucleus and the pedunculopontine nucleus, which act in conjunction to select context-dependent locomotor behaviours. Animals require different modes of movement to respond to different environments, including slow locomotion for exploratory behaviour and fast locomotion for escaping threats. Ole Kiehn and colleagues show that excitatory neurons in two brainstem nuclei, the cuneiform nucleus (CnF) and the pedunculopontine nucleus (PPN), are sufficient to support alternating locomotor stepping in mice, but only the CnF is necessary for high-speed synchronous locomotion. The activity and anatomical connectivity of these two areas are consistent with a model in which the PPN supports exploration and the CnF supports escape behaviours.