<b><i>Introduction:</i></b> Gait speed (GS) is a predictor of negative outcomes in older adults and in those in risk to develop cognitive impairment; as such, it has been associated with dementia. Studies in Latin-American older adults showing this association are scarce. This study aimed to evaluate the relationship between GS and dementia in a representative sample of Colombian older adults. <b><i>Methods:</i></b> This study is a secondary analysis from the Survey on Health, Well-Being, and Aging, SABE (from initials in Spanish: Salud, Bienestar & Envejecimiento) Colombia’s survey conducted in 2015 with a sample of 23,694 elderly adults aged 60 years or older. <b><i>Results:</i></b> A total of 19,470 participants from the SABE Colombia survey were available for analysis. The multivariate analysis shows that dementia was associated with slow GS (PR 2.39; CI 1.91–3.01) independently to the other variables (<i>p</i> < 0.001). Similarly, GS as a continuous variable shows a statistically significant association with dementia in the adjusted analysis (OR 0.06; CI 0.04–0.09; <i>p</i> < 0.001). <b><i>Conclusion:</i></b> Dementia was associated with slow GS. This finding provides evidence to include GS as a complementary parameter in the assessment of Colombian elderly adults.