Memory consolidation is well known to occur during sleep, but might start immediately after encoding new information while awake. While consolidation processes are important across the lifespan, they may be even more important to maintain memory functioning in old age. We tested whether a novel measure of information processing known as network complexity might be sensitive to post-encoding consolidation mechanisms in a sample of young, middle-aged, and older adults. Network complexity was calculated by assessing the irregularity of brain signals within a network over time using multiscale entropy. To capture post-encoding mechanisms, network complexity was estimated using functional magnetic resonance imaging (fMRI) during rest before and after encoding of picture pairs, and subtracted between the two rest periods. Participants received a five-alternative-choice memory test to assess associative memory performance. Results indicated that aging was associated with an increase in network complexity from pre- to post-encoding in the default mode network (DMN). Increases in network complexity in the DMN also were associated with better subsequent memory across all age groups. These findings suggest that network complexity is sensitive to post-encoding consolidation mechanisms that enhance memory performance. These post-encoding mechanisms may represent a pathway to support memory performance in the face of overall memory declines.