Fault-tolerance is an important design criterion for robotic systems operating in hazardous or remote environments. This paper addresses the issue of tolerating a locked joint failure in gait planning for hexapod walking machines which have symmetric structures and legs in the form of an articulated arm with three revolute joints. A locked joint failure is one for which a joint cannot move and is locked in place. If a failed joint is locked, the workspace of the resulting leg is constrained, but hexapod walking machines have the ability to continue static walking. A strategy of fault-tolerant tripod gait is proposed and, as a specific form, a periodic tripod gait is presented in which hexapod walking machines have the maximum stride length after a locked failure. The adjustment procedure from a normal gait to the proposed fault-tolerant gait is shown to demonstrate the applicability of the proposed scheme.