Cognitive flexibility is a prefrontal cortex-dependent neurocognitive process that enables behavioral adaptation in response to changes in environmental contingencies. Electrical vagus nerve stimulation (VNS) enhances several forms of learning and neuroplasticity, but its effects on cognitive flexibility have not been evaluated. In the current study, a within-subjects design was used to assess the effects of VNS on performance in a novel visual discrimination reversal learning task conducted in touchscreen operant chambers. The task design enabled simultaneous assessment of acute VNS both on reversal learning and on recall of a well-learned discrimination problem. Acute VNS delivered in conjunction with stimuli presentation during reversal learning reliably enhanced learning of new reward contingencies. Enhancement was not observed, however, if VNS was delivered during the session but was not coincident with presentation of to-be-learned stimuli. In addition, whereas VNS delivered at 30 HZ enhanced performance, the same enhancement was not observed using 10 or 50 Hz. Together, these data show that acute VNS facilitates reversal learning and indicate that the timing and frequency of the VNS are critical for these enhancing effects. In separate rats, administration of the norepinephrine reuptake inhibitor atomoxetine also enhanced reversal learning in the same task, consistent with a noradrenergic mechanism through which VNS enhances cognitive flexibility.