Gait control depends in part on cognition. This study aims to examine the separate and combined effects of episodic memory and executive function impairments on the mean value and the coefficient of variation (CoV) of stride time among non-demented older community dwellers. Based on a cross-sectional design, 1458 older community dwellers without dementia (70.6 ± 4.9 years; 49.2 % female) were recruited and separated into cognitively healthy individuals (CHI) and individuals with cognitive impairment. A score ≤5/6 on the Short Mini-Mental State Examination defined episodic memory impairment. Impaired executive function was defined by errors on the clock-drawing test. Mean value and CoV of stride time were measured by the GAITRite® system. A total of 517 participants (35.5 %) had cognitive impairment in at least one cognitive domain. Participants with memory impairment (P = 0.006) and those with combined cognitive impairments (P < 0.001) had greater (i.e., worse gait performance) mean value of stride time (P = 0.006) compared to CHI. Participants with combined cognitive impairment had a greater CoV of stride time (i.e., worse gait performance) compared to CHI (P = 0.004) and to those with separate memory impairment (P = 0.037). Among participants with combined cognitive impairments, mean value and CoV of stride time had the highest effect size (respectively, effect size = 0.49 [95 % confidence interval (CI) 0.27;0.71] and effect size = 0.40 [95 %CI 0.18;0.62]). Participants with episodic memory or executive impairments had a greater mean value and CoV of stride time compared to those with no cognitive impairment. Combined episodic memory and executive impairments exceeded the sum of separate impairments on gait performances, suggesting a complex interplay going beyond a simple additive effect.