Numerous algorithms have been proposed to allow legged robots to learn to walk.However, most of these algorithms are devised to learn walking in a straight line,which is not sufficient to accomplish any real-world mission. Here we introduce theTransferability-based Behavioral Repertoire Evolution algorithm (TBR-Evolution), anovel evolutionary algorithm that simultaneously discovers several hundreds of simplewalking controllers, one for each possible direction. By taking advantage of solutionsthat are usually discarded by evolutionary processes, TBR-Evolution is substantiallyfaster than independently evolving each controller. Our technique relies on two meth-ods: (1) novelty search with local competition, which searches for both high-performingand diverse solutions, and (2) the transferability approach, which combines simulationsand real tests to evolve controllers for a physical robot. We evaluate this new techniqueon a hexapod robot. Results show that with only a few dozen short experiments per-formed on the robot, the algorithm learns a repertoire of controllers that allows therobot to reach every point in its reachable space. Overall, TBR-Evolution introduceda new kind of learning algorithm that simultaneously optimizes all the achievablebehaviors of a robot.