We develop robust methods that allow specification, control, and transition of a multi-legged robot’s stepping pattern—its gait—during active locomotion over natural terrain. Resulting gaits emerge through the introduction of controllers that impose appropriately-placed repellors within the space of gaits, the torus of relative leg phases, thereby mitigating against dangerous patterns of leg timing. Moreover, these repellors are organized with respect to a natural cellular decomposition of gait space and result in limit cycles with associated basins that are well characterized by these cells, thus conferring a symbolic character upon the overall behavioral repertoire. These ideas are particularly applicable to four- and six-legged robots, for which a large variety of interesting and useful (and, in many cases, familiar) gaits exist, and whose tradeoffs between speed and reliability motivate the desire for transitioning between them during active locomotion. We provide an empirical instance of this gait regulation scheme by application to a climbing hexapod, whose “physical layer” sensor-feedback control requires adequate grasp of a climbing surface but whose closed loop control perturbs the robot from its desired gait. We document how the regulation scheme secures the desired gait and permits operator selection of different gaits as required during active climbing on challenging surfaces.