This paper is concerned with artificial evolution of neuro-controllers with adaptive synapses for autonomous mobile robots. The method consists of encoding on the genotype a set of local modification rules that synapses obey while the robot freely moves in the environment . The synaptic weights are not encoded on the genotype. In the experiments presented here, a "behavior-based fitness" function gives reproductive advantage to robots that can solve a sequential task. The results show that evolutionary adaptive controllers solve the task much faster and better than evolutionary standard (non-adaptive) controllers, that the method scales up well to large architectures whereas standard controllers do not, and that evolved adaptive controllers are not trivial and cannot be reduced to a fixed-weight network.