Introduction: With vulnerable aging, gait speed (GS) undergoes progressive changes, becoming slower. In this process, cognitive performance (CP) and physical function (PF) both play an important role. This study aims (1) to investigate the association between CP and PF with GS and (2) to examine whether CP and PF mediate the association between age and GS in a large sample of Brazilian older adults. Methods: A cross-sectional study analyzed 697 individuals (mean age 70.35 ± 6.86 years) from the state of Amazonas. The CP was evaluated by the COGTEL test battery, PF by the Senior Fitness Test battery, and GS with the 50-foot Walk Test. Results: Older adults with a lower CP and PF had a 70% and 86% chance of slow GS, respectively. When CP and PF were placed simultaneously as mediators, the direct effect estimated by the model revealed a non-significant relationship between age and GS. Specifically, CP and PF mediated the association between age and GS, at approximately 12% and 98%, respectively. Conclusions: CP and PF show the potential to estimate GS performance among older adults. Moreover, CP and PF indicated a negative and direct association between age and slow GS, especially PF.