The discovery that exercise regulates adult hippocampal neurogenesis, that is, the production of new neurons in the adult brain, was surprising news and changed quite fundamentally our view on how physical activity affects the brain. The everyday experience that not all athletes are necessarily smarter than more sedentary fellows and the scientific insight that adult hippocampal neurogenesis is actually a process that ranges on a very small scale raised important questions on the relevance of this finding. We propose that the exercise-related regulation of adult hippocampal neurogenesis is a qualitative rather than a quantitative event and that it is a particularly prominent and suggestive example of activity-dependent cellular plasticity. For rodents, the animals, in which most of this research has been done, cognition is almost inseparable from locomotion. Physical activity, especially exerted over longer periods of time, might indicate to the brain an increased chance of experience those situations rich in complexity and novelty that presumably benefit from more new neurons. We thus propose that it is not isolated physical activity that is "good for the brain", but physical activity in the context of cognitive challenges. This would also explain why few new neurons could be beneficial for successful aging. We here review the current stage of the knowledge how this exercise-induced regulation of neurogenesis might work.