Dysexecutive functioning, which is described as an enduring core feature of schizophrenia, has been associated with gait disorders. However, few studies have reported gait disorders in schizophrenia patients. The objective of this study was to examine the association between executive dysfunction and gait performance in recent-onset schizophrenia patients using the dual task paradigm. Thirty-two subjects participated to the study: 17 with recent-onset schizophrenia and 15 healthy age-matched controls. Executive functions were evaluated using the Frontal Assessment Battery, Stroop and Trail-Making tests. Mean values and coefficients of variation (CV) of the temporal gait parameters while single tasking (just walking) and while dual tasking (walking and forward counting, walking and backward counting, walking and verbal fluency) were measured using the SMTEC(®)-footswitch system. We focused on the CV of stride time as this measure has been shown to be the most representative parameter of higher gait control. A strong effect of the stride time was found in the group factor for the verbal fluency dual-task when compared to controls (Cohen's d mean = 1.28 and CV = 1.05). The effect was lower in the other dual tasks, and insignificant in the single task of walking. This study shows that patients exhibit higher stride-to-stride variability while dual tasking than controls. It also shows a stronger impact of verbal fluency on gait regularity compared to the other dual tasks revealing a relationship between the executive dysfunction and gait modification. Those results are in line with the idea that schizophrenia implies not only cognitive but also motor functioning and coordination impairment.