Background: The aim of this study was to investigate the association of gait speed and gait variability, an index of how much gait parameters, such as step time, fluctuate step-to-step, with risk of cognitive decline in cognitively normal elderly individuals. While high gait variability is emerging as an early indicator of dementing illnesses, there is little research on whether high gait variability predicts cognitive decline in cognitively normal elderly who have no evidence of cognitive impairment. Methods: In this 4-year prospective cohort study on 91 community-dwelling cognitively normal elderly individuals without cerebral ischemic burden or Parkinsonism, we evaluated gait speed and step time variability using a tri-axial accelerometer placed on the center of body mass, and diagnosed mild cognitive impairment (MCI) according to the International Working Group on MCI. We performed Kaplan-Meier analysis with consecutive log-rank testing for MCI-free survival by cohort-specific tertiles of gait speed; hazard ratios (HR) of incident MCI were estimated using Cox proportional hazards regression analysis adjusted for age, sex, education level, Cumulative Illness Rating Scale score, GDS score, and presence of the apolipoprotein E ε4 allele. Results: Out of the 91 participants in the baseline assessment, 87 completed one or more 2-year follow-up assessments, and the median duration of follow-up was 47.1 months. Kaplan-Meier curves of incident MCI show evident differences in risk by gait variability group (χ2 = 9.64, p = 0.002, log-rank test). Mean MCI-free survival in the high variability group was 12% shorter than in the mid-to-low tertile group (47.4 ± 1.74 [SD] vs. 54.04 ± 0.52 months), while it was comparable between gait speed groups (51.59 ± 0.70 vs. 50.64 ± 1.77 months; χ2 = 1.16, p = 0.281). In multivariate analysis, subjects with high gait variability showed about 12-fold higher risk of MCI (HR = 11.97, 95% CI = 1.29–111.37) than those with mid-to-low variability. However, those with slow gait speed showed comparable MCI risk to those with mid-to-high speed (HR = 5.04, 95% CI = 0.53–48.18). Conclusions: Gait variability may be a better predictor of cognitive decline than gait speed in cognitively normal elderly individuals without cerebral ischemic burden or Parkinsonism.