Accelerated gait decline in aging is associated with many adverse outcomes, including an increased risk for falls, cognitive decline, and dementia. Yet, the brain structures associated with gait speed, and how they relate to specific cognitive domains, are not well-understood. We examined structural brain correlates of gait speed, and how they relate to processing speed, executive function, and episodic memory in three non-demented and community-dwelling older adult cohorts (Overall N = 352), using voxel-based morphometry and multivariate covariance-based statistics. In all three cohorts, we identified gray matter volume covariance patterns associated with gait speed that included brain stem, precuneus, fusiform, motor, supplementary motor, and prefrontal (particularly ventrolateral prefrontal) cortex regions. Greater expression of these gray matter volume covariance patterns linked to gait speed were associated with better processing speed in all three cohorts, and with better executive function in one cohort. These gray matter covariance patterns linked to gait speed were not associated with episodic memory in any of the cohorts. These findings suggest that gait speed, processing speed (and to some extent executive functions) rely on shared neural systems that are subject to age-related and dementia-related change. The implications of these findings are discussed within the context of the development of interventions to compensate for age-related gait and cognitive decline.