A series of recent studies identified key structures in the mesencephalic locomotor region and the caudal brainstem of mice involved in the initiation and control of slow (exploratory) and fast (escape-type) locomotion and gait. However, the interactions of these brainstem centers with each other and with the spinal locomotor circuits are poorly understood. Previously we suggested that commissural and long propriospinal interneurons are the main targets for brainstem inputs adjusting gait (Danner et al., 2017). Here, by extending our previous model, we propose a connectome of the brainstem-spinal circuitry and suggest a mechanistic explanation of the operation of brainstem structures and their roles in controlling speed and gait. We suggest that brainstem control of locomotion is mediated by two pathways, one controlling locomotor speed via connections to rhythm generating circuits in the spinal cord and the other providing gait control by targeting commissural and long propriospinal interneurons.