Fear of falling (FOF) and gait disorders represent both prevalent symptoms in patients with multiple sclerosis (MS); however, the association between FOF and higher level of gait control (HLGC) has not been studied in MS. This study aims to assess the association between FOF and HLGC in patients with MS. HLGC was assessed by stride time variability (STV) during single and dual-tasks (forward counting, backward counting, categorical verbal fluency and literal verbal fluency) and FOF was quantified by the falls efficacy scale-international (FES-I). Seventy-one patients (age: 39.27 ± 9.77 years; 63 % female) were included in this cross-sectional study (Expanded Disability Status Scale (median): 2.00) with a low prevalence of FOF (FES-I: 21.52 ± 8.37). The mean gait speed was 1.19 ± 0.23 m/s with a STV of 2.35 ± 1.68 % during single walking task. STV during single task and the dual tasks of forward counting and backward counting were associated with the FES-I in the univariable linear regression models (p ≤ 0.001), but only STV while backward counting (β: 0.42, [0.18;0.66]) was associated with FOF in the multivariable model (adjusted for age, gender, previous fall, Expanded Disability Status Scale and gait speed). These findings indicate that FOF is associated with STV while backward counting, a marker of HLGC in relationship with working memory in a MS population including a majority of low disabled patients.