VNS is an adjunctive neuromodulation therapy for patients with drug-refractory epilepsy. The antiseizure effect of VNS is thought to be related to a diffuse modulation of functional connectivity but remains to be confirmed. To investigate electroencephalographic (EEG) metrics of functional connectivity in patients with drug-refractory epilepsy treated by vagus nerve stimulation (VNS), between VNS-stimulated "ON" and nonstimulated "OFF" periods and between responder (R) and nonresponder (NR) patients. Scalp-EEG was performed for 35 patients treated by VNS, using 21 channels and 2 additional electrodes on the neck to detect the VNS stimulation. Patients were defined as VNS responders if a reduction of seizure frequency of ∼50% was documented. We analyzed the synchronization in EEG time series during "ON" and "OFF" periods of stimulation, using average phase lag index (PLI) in signal space and phase-locking value (PLV) between 10 sources. Based on graph theory, we computed brain network models and analyzed minimum spanning tree (MST) for responder and nonresponder patients. Among 35 patients treated by VNS for a median time of 7 years (range 4 months to 22 years), 20 were R and 15 were NR. For responder patients, PLI during ON periods was significantly lower than that during OFF periods in delta ( = 0.009), theta ( = 0.02), and beta ( = 0.04) frequency bands. For nonresponder patients, there were no significant differences between ON and OFF periods. Moreover, variations of seizure frequency with VNS correlated with the PLI OFF/ON ratio in delta ( = 0.02), theta ( = 0.04), and beta ( = 0.03) frequency bands. Our results were confirmed using PLV in theta band ( < 0.05). No significant differences in MST were observed between R and NR patients. The correlation between VNS-induced interictal EEG time-series desynchronization and decrease in seizure frequency suggested that VNS therapeutic impact might be related to changes in interictal functional connectivity. Impact statement Electroencephalography (EEG) desynchronization has been proposed to be a mechanism for antiepileptic effect of vagus nerve stimulation (VNS). We measured interictal EEG time-series synchronization during stimulated (ON) and nonstimulated (OFF) periods in epileptic patients treated by VNS. Phase lag index differences between ON and OFF periods were measured in delta, theta, and beta bands only in responder patients. To our knowledge, our study is the first to statistically correlate interictal cortical desynchronization during ON periods with reduction in seizure frequency. Our result supports the hypothesis that the antiseizure effect of VNS is mediated by cortical desynchronization.