Adult neurogenesis is reduced during aging and impaired in disorders of stress, memory, and cognition though its normal function remains unclear. Moreover, a systems level understanding of how a small number of young hippocampal neurons could dramatically influence brain function is lacking. We examined whether adult neurogenesis sustains hippocampal connections cumulatively across the life span. Long-term suppression of neurogenesis as occurs during stress and aging resulted in an accelerated decline in hippocampal acetylcholine signaling and a slow and progressing emergence of profound working memory deficits. These deficits were accompanied by compensatory reorganization of cholinergic dentate gyrus inputs with increased cholinergic innervation to the ventral hippocampus and recruitment of ventrally projecting neurons by the dorsal projection. While increased cholinergic innervation was dysfunctional and corresponded to overall decreases in cholinergic levels and signaling, it could be recruited to correct the resulting memory dysfunction even in old animals. Our study demonstrates that hippocampal neurogenesis supports memory by maintaining the septohippocampal cholinergic circuit across the lifespan. It also provides a systems level explanation for the progressive nature of memory deterioration during normal and pathological aging and indicates that the brain connectome is malleable by experience.