Recent research highlights the association of gait and cognition in older adults but a stronger understanding is needed to discern coincident pathophysiology, patterns of change, examine underlying mechanisms and aid diagnosis. This structured review mapped associations and predictors of gait and cognition in older adults with and without cognitive impairment, and Parkinson's disease. Fifty papers out of an initial yield of 22,128 were reviewed and a model of gait guided analysis and interpretation. Associations were dominated by the pace domain of gait; the most frequently studied domain. In older adults pace was identified as a predictor for cognitive decline. Where comprehensive measurement of gait was conducted, more specific pathological patterns of association were evident highlighting the importance of this approach. This review confirmed a robust association between gait and cognition and argues for a selective, comprehensive measurement approach. Results suggest gait may be a surrogate marker of cognitive impairment and cognitive decline. Understanding the specific nature of this relationship is essential for refinement of diagnostics and development of novel therapies.