Combining physical and cognitive training has been suggested to promote further benefits on brain and cognition, which could include synergistic improvement of hippocampal neuroplasticity. In this paper, we investigated whether treadmill exercise followed by a working memory training in the water maze increase adult hippocampal neurogenesis to a greater extent than either treatment alone. Our results revealed that ten days of scheduled running enhance cell proliferation/survival in the short-term as well as performance in the water maze. Moreover, exercised mice that received working memory training displayed more surviving dentate granule cells compared to those untreated or subjected to only one of the treatments. According to these findings, we suggest that combining physical and cognitive stimulation yield synergic effects on adult hippocampal neurogenesis by extending the pool of newly-born cells and subsequently favouring their survival. Future research could take advantage from this non-invasive, multimodal approach to achieve substantial and longer-lasting enhancement in adult hippocampal neurogenesis, which might be relevant for improving cognition in healthy or neurologically impaired conditions.