We here show that living in a stimulus-rich environment (ENR) improves water maze learning with respect to specific key indicators that in previous loss-of-function experiments have been shown to rely on adult hippocampal neurogenesis. Analyzing the strategies employed by mice to locate the hidden platform in the water maze revealed that ENR facilitated task acquisition by increasing the probability to use effective search strategies. ENR also enhanced the animals' behavioral flexibility, when the escape platform was moved to a new location. Treatment with temozolomide, which is known to reduce adult neurogenesis, abolished the effects of ENR on both acquisition and flexibility, while leaving other aspects of water maze learning untouched. These characteristic effects and interdependencies were not seen in parallel experiments with voluntary wheel running (RUN), a second pro-neurogenic behavioral stimulus. Since the histological assessment of adult neurogenesis is by necessity an end-point measure, the levels of neurogenesis over the course of the experiment can only be inferred and the present study focused on behavioral parameters as analytical endpoints. Although the correlation of physical activity with precursor cell proliferation and of learning and the survival of new neurons is well established, how the specific functional effects described here relate to dynamic changes in the stem cell niche remains to be addressed. Nevertheless, our findings support the hypothesis that adult neurogenesis is a critical mechanism underlying the beneficial effects of leading an active live, rich in experiences.