To investigate the association between gait speed (GS), cadence (CAD), gait stability ratio (GSR), and body balance (BB) with falls in a large sample of older adults. The analysis included 619 individuals—305 men and 314 women (69.50 ± 5.62 years)—residing in the Autonomous Region of Madeira, Portugal. Mobility in GS, CAD, and GSR was assessed using the 50-foot walk test and BB by the Fullerton Advanced Balance scale. The frequency of falls was obtained by self-report. Linear regression analysis showed that higher performance in GS and BB was able to reduce the risk of falling by up to 0.34 and 0.44 times, respectively. An increase in the GSR value enhanced the risk of falling by up to 0.10 times. Multinomial analysis indicated that, in relation to the highest tertile (reference), older adults classified with GS and BB performance in the lowest tertile (lowest) had an increased chance (OR) of falling by up to 149.3% and 48.8%, respectively. Moreover, in relation to the highest tertile, the performance of the GSR classified in the lowest and medium tercile showed an increase in the chance of falling by up to 57.4% and 56.4%, respectively.