Locomotion is a universal motor behavior that is expressed as the output of many integrated brain functions. Locomotion is organized at several levels of the nervous system, with brainstem circuits acting as the gate between brain areas regulating innate, emotional, or motivational locomotion and executive spinal circuits. Here we review recent advances on brainstem circuits involved in controlling locomotion. We describe how delineated command circuits govern the start, speed, stop, and steering of locomotion. We also discuss how these pathways interface between executive circuits in the spinal cord and diverse brain areas important for context-specific selection of locomotion. A recurrent theme is the need to establish a functional connectome to and from brainstem command circuits. Finally, we point to unresolved issues concerning the integrated function of locomotor control. Expected final online publication date for the Annual Review of Neuroscience, Volume 45 is July 2022. Please see http://www.annualreviews.org/page/journal/pubdates for revised estimates.