Gait decline is common among older adults and is a risk factor for adverse outcomes. Poor gait performance in dual-task conditions, such as walking while performing a secondary cognitive interference task, is associated with increased risk of frailty, disability, and death. Yet, the functional neural substrates that support locomotion are not well established. We examined the functional connectivity associated with gait velocity in single- (normal pace walking) and dual-task (walking while talking) conditions using resting-state functional Magnetic Resonance Imaging (fMRI). We acquired 6 minutes of resting-state fMRI data in 30 cognitively healthy older adults. Independent components analyses were performed to separate resting-state fMRI data into group-level statistically independent spatial components that correlated with gait velocity in single- and dual-task conditions. Gait velocity in both task conditions was associated with similar functional connectivity in sensorimotor, visual, vestibular, and left fronto-parietal cortical areas. Compared to gait velocity in the single-task condition, the networks associated with gait velocity in the dual-task condition were associated with greater functional connectivity in supplementary motor and prefrontal regions. Our findings show that there are partially overlapping functional networks associated with single- and dual-task walking conditions. These initial findings encourage the future use of resting-state fMRI as tool in developing a comprehensive understanding of age-related mobility impairments.