It is argued that competitive co-evolution is a viable methodology for developing truly autonomous and intelligent machines capable of setting their own goals in order to face new and continuously changing challenges. The paper starts giving an introduction to the dynamics of competitive co-evolutionary systems and reviews their relevance from a computational perspective. The method is then applied to two mobile robots, a predator and a prey, which quickly and autonomously develop efficient chase and evasion strategies. The results are then explained and put in a long-term framework resorting to a visualization of the Red Queen effect on the fitness landscape. Finally, comparative data on different selection criteria are used to indicate that co-evolution does not optimize "intuitive" objective criteria.