Random diffusion is shown to be an important mechanism on fostering cooperative behavior among simple agents (memoryless, unconditional cooperators or defectors) living on a spatially structured environment. In particular, under the Prisoner's Dilemma framework, when allowing the agents to move with the simple ``always-move'' rule, we find that cooperative behavior is not only possible but may even be enhanced. In addition, for a broad range of densities, mobile cooperators can more easily invade a population of mobile defectors, when compared with the fully viscous, immobile case. Thus, such simple mobility pattern may have played a fundamental role both in the onset and development of cooperative behavior, paving the way to more complex, individual and group, motility rules.