Evolutionary Algorithms (EAs) now provide mature optimization tools that have successfully been applied to many problems, from designing antennas to complete robots, and provided many human-competitive results. In robotics, the integration of EAs within the engineer's toolbox made tremendous progress in the last 20 years and proposes new methods to address challenging problems in various setups: modular robotics, swarm robotics, robotics with non-conventional mechanics (e.g. high redundancy, dynamic motion, multi-modality), etc. This book takes its roots in the workshop on "New Horizons in Evolutionary Design of Robots" that brought together researchers from Computer Science and Robotics during the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-2009) in Saint Louis (USA). This book features extended contributions from the workshop, thus providing various examples of current problems and applications, with a special emphasis on the link between Computer Science and Robotics. It also provides a comprehensive and up-to-date introduction to Evolutionary Robotics after 20 years of maturation as well as thoughts and considerations from several major actors in the field. This book offers a comprehensive introduction to the current trends and challenges in Evolutionary Robotics for the next decade.