We aimed to examine associations between cognitive vulnerability and gait speed (GS) in a large older sample. A cross-sectional study analyzed data from the “Health, Lifestyle and Fitness in Adults and Seniors in Amazonas” (SEVAAI) project. In total, 697 participants were included (mean age 70.35 ± 6.86 years). Usual and fast GS were evaluated, and cognitive performance was examined by the COGTEL test battery. There was a positive and large correlation between cognition (COGTEL score) and usual GS (r = 0.510; p < 0.001) and fast GS (r = 0.503; p < 0.001). The usual GS, as a continuous variable, indicated a chance of improved cognitive performance by up to 55%, and fast GS by up to 82%. After controlling for potential confounders (i.e., sex, age, MMSE and years of education), usual and fast GS indicated a chance of improving cognition, respectively, in 57% and 85%. Analysis of GS in quartiles (Q) showed high and significant associations between usual and fast GS and cognitive vulnerability. GS classified as Q1 (slower), Q2 and Q3 represented a greater chance of presenting cognitive deficits, respectively, than in participants with both GS classified as Q4 (highest). Cognitive vulnerability was associated with low GS. Usual and fast GS can be used as complementary measures for the evaluation of cognitively normal Brazilian older adults.