Perception can be refined by experience up to certain limits. It is unclear if limitations are absolute or could be partially overcome via enhanced neuromodulation and/or plasticity. Recent studies highlight the utility of peripheral nerve stimulation - specifically vagus nerve stimulation (VNS) - for altering neural activity and augmenting experience-dependent plasticity, although little is known about central mechanisms recruited by VNS. Here we developed an auditory discrimination task for mice implanted with a VNS electrode. VNS occurring during behavior gradually improved discrimination abilities beyond the level achieved by training alone. Using two-photon imaging, we identified changes to auditory cortical responses and activation of cortically-projecting cholinergic axons with VNS. Anatomical and optogenetic experiments revealed that VNS seemed to enhance task performance via activation of the central cholinergic system. These results highlight the importance of cholinergic modulation for the efficacy of VNS, perhaps enabling further refinement of VNS methodology for clinical conditions.