This study, conducted on a large sample of older adults at elevated fall risk (1), aimed to verify statistical differences in gait stability ratio (GSR) and body balance (BB) according to sex, (2) to examine and compare GSR and BB performance between older adult fallers and non-fallers, (3) to determine an association between GSR and BB according to the history of falls, and (4) to explore whether GSR and BB mediate the association between sex and falls. We included 619 individuals (69.8 ± 5.6 years) living in the Autonomous Region of Madeira, Portugal. The frequency of falls was obtained by self-report. BB was determined by the Fullerton Advanced Balance scale, while GSR was established by dividing cadence by gait speed and data collected during the 50-foot walk test. Males indicated a lower prevalence of falls in the last 12 months (23.6%), while females had a higher score (48.7%), as well as a lower balance performance (p < 0.001) and higher GSR scores (p < 0.001). Lower BB control (p < 0.001), as well as higher GSR, were more expressive for fallers (p < 0.001). We found a large, negative and significant correlation between GSR and BB for historical falls (r = −0.560; p < 0.001), and between male and female cohorts (r = −0.507; p < 0.001). The total effect of sex on falls mediated by GSR and BB was 16.4%. Consequently, GSR and BB mediated this association by approximately 74.0% and 22.5%, respectively.