This study aimed to clarify the neural substrates of behavioral switch and restart costs in intermittently instructed task-switching paradigms. Event-related potentials (ERPs) were recorded while participants were intermittently cued to switch or repeat their categorization rule (Switch task), or else they performed two perceptually identical control conditions (NoGo and Oddball). The three tasks involved different task-sets with distinct stimulus-response associations in each, but identical visual stimulation, consisting of frequent colored shapes (p = 0.9) and randomly interspersed infrequent black shapes (p = 0.1; ‘+’ and ‘x’ symbols). Behavioral restart costs were observed in the first target responses following all black shapes in the Switch and NoGo tasks – but not in the Oddball task – and corresponded with enhanced fronto-centrally distributed early cue-locked P3 activity (peak latency 325–375 ms post-cue onset at the vertex). In turn, behavioral switch costs were associated with larger late cue-locked P3 amplitudes in the Switch task only (peak latency 400–450 ms post-cue onset at mid-parietal sites). Together with our information theoretical estimations, ERP results suggested that restart and switch costs indexed two neural mechanisms related to the preparatory resolution of uncertainty: (1) the intermittent re-activation of task-set information, and (2) the updating of stimulus-response mappings within an active task set, as indexed by early and late cue-locked P3 activations, respectively. In contrast, target-locked P3 activations reflected a functionally distinct mechanism related to the implementation of task-set information. We conclude that task-switching costs consist of both switch-specific and switch-unspecific processes during the preparation and execution stages of task performance.