Dual task-related changes in gait are considered as a sensitive and a specific marker of adverse effects of cognitive impairment on the highest levels of gait control. No study has examined the longitudinal association between gait performance while dual tasking and the occurrence of cognitive decline. This study aims to examine the association of stride time parameters (i.e., mean value and coefficient of variation (CoV)) during single and dual tasking with the occurrence of cognitive decline in non-demented older community dwellers. A total of 56 non-demented community dwellers were recruited in a longitudinal prospective cohort study. Mini-Mental Status Examination (MMSE) scores at baseline assessment and at 5-year follow-up assessment, and mean value and CoV of stride time at self-selected usual pace, while usual walking and dual tasking (i.e., counting backward and verbal fluency task) at baseline assessment were recorded. Variation (i.e., delta) of MMSE score from baseline to follow-up assessment as well as of stride time parameters from single to dual task was used as outcomes. Worse stride time values were reported while dual tasking compared to single tasking (P < 0.03). An increase of mean value, CoV, and delta of CoV of stride time was associated with an increased delta MMSE while performing verbal fluency task (P < 0.05). Worsening stride time parameters while performing a verbal fluency task at baseline assessment was associated with decline in MMSE score during the 5-year follow-up period in this sample of older community dwellers.