Increasing evidence suggests that regular exercise improves brain health and promotes synaptic plasticity and hippocampal neurogenesis. Exercise improves learning, but specific mechanisms of information processing influenced by physical activity are unknown. Here, we report that voluntary running enhanced the ability of adult (3 months old) male C57BL/6 mice to discriminate between the locations of two adjacent identical stimuli. Improved spatial pattern separation in adult runners was tightly correlated with increased neurogenesis. In contrast, very aged (22 months old) mice had impaired spatial discrimination and low basal cell genesis that was refractory to running. These findings suggest that the addition of newly born neurons may bolster dentate gyrus-mediated encoding of fine spatial distinctions.