Animals display naturally robust locomotion de- signs which enable them to move on rugged terrains and even adapt to injuries. Most of the robots do not possess such robustness and are rendered useless if they get structurally damaged. In this paper, it is shown that such adapting ability can be introduced in robot’s locomotion, if damaged, by evolving optimal gaits through genetic algorithm (GA). A hexapod robot simulation was used to test the gaits generated by GA. Simulation results have proven that the evolved gait enables a hexapod to move effectively with one leg damaged. This technique will increase the reliability and effectiveness of autonomous robots in areas hostile to humans.