A strategy for fault-tolerant gaits of autonomous legged robots is proposed. A legged robot is considered to be fault tolerant with respect to a given failure if it is guaranteed to be capable of walking maintaining its static stability after the occurrence of the failure. The failure concerned in this paper is a locked joint failure for which a joint in a leg cannot move and is locked in place. If a failed joint is locked, the workspace of the resulting leg is constrained, but legged robots have fault tolerance capability to continue static walking. An algorithm for generating fault-tolerant gaits is described and, especially, periodic gaits are presented for forward walking of a hexapod robot with a locked joint failure. The leg sequence and the formula of the stride length are analytically driven based on gait study and robot kinematics. The transition procedure from a normal gait to the proposed fault-tolerant gait is shown to demonstrate the applicability of the proposed scheme.