A gait generation device for generating a desired gait which includes floating periods in which all the legs 2, 2 of a legged mobile robot 1 float in the air and landing periods in which at least one leg 2 is in contact with a floor which appear alternately generates the desired gait in such a manner that, at least when shifting from the floating period to the landing period, the velocity of an end portion 22 of a landing leg with respect to the floor and the acceleration thereof with respect to the floor is substantially 0 at the instant of landing. After both the velocity of the end portion of the leg with respect to the floor and the acceleration thereof with respect to the floor are determined to be substantially 0, a movement of the body of the robot with the desired gait is determined in such a manner that the horizontal component of a moment produced about the desired ZMP by the resultant force of gravity and an inertial force applied to the robot 1 is substantially 0. This eliminates the landing impact.