Brain-wide neural circuits enable bi- and quadrupeds to express adaptive locomotor behaviors in a context- and state-dependent manner, e.g., in response to threats or rewards. These behaviors include dynamic transitions between initiation, maintenance and termination of locomotion. Advances within the last decade have revealed an intricate coordination of these individual locomotion phases by complex interaction of multiple brain circuits. This review provides an overview of the neural basis of state-dependent modulation of locomotion initiation, maintenance and termination, with a focus on insights from circuit-centered studies in rodents. The reviewed evidence indicates that a brain-wide network involving excitatory circuit elements connecting cortex, midbrain and medullary areas appears to be the common substrate for the initiation of locomotion across different higher-order states. Specific network elements within motor cortex and the mesencephalic locomotor region drive the initial postural adjustment and the initiation of locomotion. Microcircuits of the basal ganglia, by implementing action-selection computations, trigger goal-directed locomotion. The initiation of locomotion is regulated by neuromodulatory circuits residing in the basal forebrain, the hypothalamus, and medullary regions such as locus coeruleus. The maintenance of locomotion requires the interaction of an even larger neuronal network involving motor, sensory and associative cortical elements, as well as defined circuits within the superior colliculus, the cerebellum, the periaqueductal gray, the mesencephalic locomotor region and the medullary reticular formation. Finally, locomotor arrest as an important component of defensive emotional states, such as acute anxiety, is mediated via a network of survival circuits involving hypothalamus, amygdala, periaqueductal gray and medullary premotor centers. By moving beyond the organizational principle of functional brain regions, this review promotes a circuit-centered perspective of locomotor regulation by higher-order states, and emphasizes the importance of individual network elements such as cell types and projection pathways. The realization that dysfunction within smaller, identifiable circuit elements can affect the larger network function supports more mechanistic and targeted therapeutic intervention in the treatment of motor network disorders.