Cognitive slowing is a prevalent symptom observed in Gulf War Illness (GWI). The present study assessed the extent to which functional connectivity between dorsolateral prefrontal cortex (DLPFC) and other task-relevant brain regions was predictive of GWI-related cognitive slowing. GWI patients (n = 54) and healthy veteran controls (n = 29) were assessed on performance of a processing speed task (the Digit Symbol Substitution Task; DSST) while undergoing functional magnetic resonance imaging (fMRI). GWI patients were slower on the DSST relative to controls. Bilateral DLPFC connectivity with task-relevant nodes was altered in GWI patients compared to healthy controls during DSST performance. Moreover, hyperconnectivity in these networks predicted GWI-related increases in reaction time on the DSST, whereas hypoconnectivity did not. These results suggest that GWI-related cognitive slowing reflects reduced efficiency in cortical networks.