A method for a stair tracking for modeled and perceived terrain includes receiving, at data processing hardware, sensor data about an environment of a robot. The method also includes generating, by the data processing hardware, a set of maps based on voxels corresponding to the received sensor data. The set of maps includes a ground height map and a map of movement limitations for the robot. The map of movement limitations identifies illegal regions within the environment that the robot should avoid entering. The method further includes generating a stair model for a set of stairs within the environment based on the sensor data, merging the stair model and the map of movement limitations to generate an enhanced stair map, and controlling the robot based on the enhanced stair map or the ground height map to traverse the environment.