Background: Physical exercise in early adulthood and mid-life improves cognitive function and enhances brain plasticity, but the effects of commencing exercise in late adulthood are not well-understood. Method: We investigated the effects of voluntary exercise in the restoration of place recognition memory in aged rats and examined hippocampal changes of synaptic density and neurogenesis. Results: We found a highly selective age-related deficit in place recognition memory that is stable across retest sessions and correlates strongly with loss of hippocampal synapses. Additionally, 12 weeks of voluntary running at 20 months of age removed the deficit in the hippocampally dependent place recognition memory. Voluntary running restored presynaptic density in the dentate gyrus and CA3 hippocampal subregions in aged rats to levels beyond those observed in younger animals, in which exercise had no functional or synaptic effects. By contrast, hippocampal neurogenesis, a possible memory-related mechanism, increased in both young and aged rats after physical exercise but was not linked with performance in the place recognition task. We used graph-based network analysis based on synaptic covariance patterns to characterize efficient intrahippocampal connectivity. This analysis revealed that voluntary running completely reverses the profound degradation of hippocampal network efficiency that accompanies sedentary aging. Furthermore, at an individual animal level, both overall hippocampal presynaptic density and subregional connectivity independently contribute to prediction of successful place recognition memory performance. Conclusions: Our findings emphasize the unique synaptic effects of exercise on the aged brain and their specific relevance to a hippocampally based memory system for place recognition.