This paper describes our studies in the legged robots research area and the development of the LegGen System, that is used to automatically create and control stable gaits for legged robots into a physically based simulation environment. The parameters used to control the robot are optimized using Genetic Algorithms (GA). Comparisons between different fitness functions were accomplished, indicating how to compose a better multi-criterion fitness function to be used in the gait control of the legged robots. The best gait control solution and the best robot model were selected in order to help us to build a real robot in the future. The results also showed that it is possible to generate stable gaits using GA in an efficient manner.