We aimed to investigate the relationship of fall risk with spatiotemporal gait variables and variability in community-dwelling older adults and identify the key predictors of fall risk. A total of 303 older adults were classified into the fall-risk and non-fall-risk groups based on their Short Physical Performance Battery scores. The stance phase time, double stance time, stride length, step width, velocity, cadence, and coefficient of variation (CV) for each variable were measured on a treadmill at the preferred speed and 20% increased walking speed. The results showed that the fall-risk group had a significantly increased stance phase and double stance time, while the stride length, velocity, and cadence were significantly reduced compared to the non-fall-risk group at both speeds. Additionally, the CV for most variables was significantly higher in the fall-risk group. Notably, the step width variability was higher in the fall-risk group under both speed conditions and showed greater discriminative power at increased walking speed. Thus, gait variability, particularly step width variability, is a crucial predictor of fall risk. The increased variability observed in the fall-risk group at higher walking speed suggests that it could be a useful early indicator for predicting fall risk.