Neural desynchronization was shown as a key mechanism of vagus nerve stimulation (VNS) action in epilepsy, and EEG synchronization measures are explored as possible response biomarkers. Since brain functional organization in sleep shows different synchrony and network properties compared to wakefulness, we aimed to explore the effects of acute VNS on EEG-derived measures in the two different states of vigilance. EEG epochs were retrospectively analyzed from twenty-four VNS-treated epileptic patients (11 responders, 13 non-responders) in calm wakefulness and stage N2 sleep. Weighted Phase Lag Index (wPLI) was computed as connectivity measure of synchronization, for VNS OFF and VNS ON conditions. Global efficiency (GE) was computed as a network measure of integration. Ratios OFF/ON were obtained as desynchronization/de-integration index. Values were compared between responders and non-responders, and between EEG states. ROC curve and area-under-the-curve (AUC) analysis was performed for response classification. In responders, stronger VNS-induced theta desynchronization (p < 0.05) and decreased GE (p < 0.05) were found in sleep, but not in wakefulness. Theta sleep wPLI Ratio OFF/ON yielded an AUC of 0.825, and 79% accuracy as a response biomarker if a cut-off value is set at 1.05. Considering all patients, the VNS-induced GE decrease was significantly more important in sleep compared to awake EEG state (p < 0.01). In conclusion, stronger sleep EEG desynchronization in theta band distinguishes responders to VNS therapy from non-responders. VNS-induced reduction of network integration occurs significantly more in sleep than in wakefulness.