Cognitive demands for postural control increase with aging and cognitive-motor interference (CMI) exists for a number of walking situations, especially with visuo-spatial cognitive tasks. Such interference also influences spatial learning abilities among older adults; however, this is rarely considered in research on aging in spatial navigation. We posited that visually and physically exploring an unknown environment may be subject to CMI for older adults. We investigated potential indicators of postural control interfering with spatial learning. Given known associations between age-related alterations in gait and brain structure, we also examined potential neuroanatomical correlates of this interference. Fourteen young and 14 older adults had to find an invisible goal in an unfamiliar, real, ecological environment. We measured walking speed, trajectory efficiency (direct route over taken route) and goal fixations (proportion of visual fixations toward the goal area). We calculated the change in walking speed between the first and last trials and adaptation indices for all three variables to quantify their modulation across learning trials. All participants were screened with a battery of visuo-cognitive tests. Eighteen of our participants (10 young, 8 older) also underwent a magnetic resonance imaging (MRI) examination. Older adults reduced their walking speed considerably on the first, compared to the last trial. The adaptation index of walking speed correlated positively with those of trajectory efficiency and goal fixations, indicating a reduction in resource sharing between walking and encoding the environment. The change in walking speed correlated negatively with gray matter volume in superior parietal and occipital regions and the precuneus. We interpret older adults' change in walking speed as indicative of CMI, similar to dual task costs. This is supported by the correlations between the adaptation indices and between the change in walking speed and gray matter volume in brain regions that are important for navigation, given that they are involved in visual attention, sensory integration and encoding of space. These findings under ecological conditions in a natural spatial learning task question what constitutes dual tasking in older adults and they can lead future research to reconsider the actual cognitive burden of postural control in aging navigation research.