In this paper, we explore the capability of Genetic Algorithms (GA) to evolve walking gaits for an eight-legged robot with three degrees of freedom per leg when one or more of its legs are disabled. This work is an extension of previous research completed by Parker, Isak and O’Connor, which found success in combining GAs and Incremental Evolution to evolve near-optimal gaits for an arachnid-inspired robot. They completed the learning in two increments. In the first increment, individual leg cycles were learned, while the second increment facilitated the learning of overall gait coordination. The first increment of our work is the same as in the previous work. We use a Cyclic Genetic Algorithm (CGA) to first learn pulse instructions for the servo motors on each leg to generate leg cycles. In the second increment, which we have improved upon, we use a GA to select the best combination of leg cycles for each leg, learn the timing to execute each leg cycle, and coordinate all of the leg cycles into a single gait. Our improvements in the second increment include adjusting the fitness function and robot model to better reflect how faults affect performance. The training involved disabling up to two legs on the robot in simulation and learning a gait that adapts to these faults. We compare these fault-tolerant gaits to a near-optimal fully-functioning gait. Testing in simulation confirmed the viability of this method.