Different memory systems offer distinct advantages to navigational behavior. The hippocampus forms complex associations between environmental stimuli, enabling flexible navigation through space. In contrast, the dorsal striatum associates discrete cues and favorable behavioral responses, enabling habit-like, automated navigation. While these two systems often complement one another, there are instances where striatal-dependent responses (e.g. approach a cue) conflict with hippocampal representations of spatial goals. In conflict situations, preference for spatial vs. response strategies varies across individuals and depends on previous experience, plasticity and the integrity of these two memory systems. Here, we investigated the role of adult hippocampal neurogenesis and exercise on mouse search strategies in a water maze task that can be solved with either a hippocampal-dependent place strategy or a striatal-dependent cue-response strategy. We predicted that inhibiting adult neurogenesis would impair hippocampal function and shift behavior towards striatal-dependent cue responses. However, blocking neurogenesis in a transgenic nestin-TK mouse did not affect strategy choice. We then investigated whether a pro-neurogenic stimulus, running, would bias mice towards hippocampal-dependent spatial strategies. While running indeed promoted spatial strategies, it did so even when neurogenesis was inhibited in nestin-TK mice. These findings indicate that exercise-induced increases in neurogenesis are not always required for enhanced cognitive function. Furthermore, our data identify exercise as a potentially useful strategy for promoting flexible, cognitive forms of memory in habit-related disorders that are characterized by excessive responding to discrete cues.