In this paper the application of Genetic Algorithms is presented to the task of designing a humanoid robot able to exhibit an efficient walking. This task is presented as an optimization problem. The objective function is the so-called Specific Cost of Transportation and the restrictions of the problem are based on the Limit Cycle Walking stability criterion. The mechanical design of the prototype and its walking trajectories are inspired on passive dynamic walkers. A basic genetic algorithm was used to find: the optimized mechanical parameters for design, the walking trajectories and the feedback gains used in the control of the current prototype.