Examples method and devices for automatic gait transition are described herein. In an example embodiment, a computing system may identify gaits for the robotic device to perform in response to receiving an input for the robotic device to move at a velocity. The system may determine criteria for selecting a gait from the identified gaits for the robotic device to perform based on sensor data of the environment (e.g., slope and terrain) and based on the state of the robotic device. The system may modify the set of criteria based on prior operation of the robotic device in respective environments similar to the environment. Responsive to determining the criteria for selecting a gait, the computing system may determine whether the identified gaits include a gait that enables the robotic device to move at the velocity according to the set of criteria, and provide instructions to operate based on the determination.