Successful consolidation of associative memories relies on the coordinated interplay of slow oscillations and sleep spindles during non-rapid eye movement (NREM) sleep. This enables the transfer of labile information from the hippocampus to permanent memory stores in the neocortex. During senescence, the decline of the structural and functional integrity of the hippocampus and neocortical regions is paralleled by changes of the physiological events that stabilize and enhance associative memories during NREM sleep. However, the currently available evidence is inconclusive as to whether and under which circumstances memory consolidation is impacted during aging. To approach this question, 30 younger adults (19–28 years) and 36 older adults (63–74 years) completed a memory task based on scene–word associations. By tracing the encoding quality of participants’ individual memory associations, we demonstrate that previous learning determines the extent of age-related impairments in memory consolidation. Specifically, the detrimental effects of aging on memory maintenance were greatest for mnemonic contents of intermediate encoding quality, whereas memory gain of poorly encoded memories did not differ by age. Ambulatory polysomnography (PSG) and structural magnetic resonance imaging (MRI) data were acquired to extract potential predictors of memory consolidation from each participant’s NREM sleep physiology and brain structure. Partial Least Squares Correlation was used to identify profiles of interdependent alterations in sleep physiology and brain structure that are characteristic for increasing age. Across age groups, both the ‘aged’ sleep profile, defined by decreased slow-wave activity (0.5–4.5 Hz), and a reduced presence of slow oscillations (0.5–1 Hz), slow, and fast spindles (9–12.5 Hz; 12.5–16 Hz), as well as the ‘aged’ brain structure profile, characterized by gray matter reductions in the medial prefrontal cortex, thalamus, entorhinal cortex, and hippocampus, were associated with reduced memory maintenance. However, inter-individual differences in neither sleep nor structural brain integrity alone qualified as the driving force behind age differences in sleep-dependent consolidation in the present study. Our results underscore the need for novel and age-fair analytic tools to provide a mechanistic understanding of age differences in memory consolidation.