This paper presents a strategy for generating fault-tolerant gaits of hexapod walking robots. A multi-legged robot is considered to be fault-tolerant with respect to a given failure if it is capable of continuing its walking after the occurrence of a failure, maintaining its static stability. 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. The kinematic condition for the existence of fault-tolerant gaits is derived for straight-line walking of a hexapod robot on even terrain. 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 stride length formula are analytically driven based on gait study and robot kinematics. A case study on post-failure walking of a hexapod robot with the wave gait is shown to demonstrate the applicability of the proposed method.