Studies have indicated that vagus nerve stimulation (VNS) enhances extinction learning in rodent models. Here, we investigated if pairing VNS with the conditioned stimulus is required for the enhancing effects of VNS. Adult Sprague-Dawley rats were exposed to intense stress followed by fear conditioning training to produce resistant fear. Rats were then implanted with a cuff electrode around the left vagus. After recovery, rats underwent extinction training paired with VNS (0.5 s, 0.8 mA, 100 µs, and 30 Hz) or with Sham VNS (0 mA). VNS rats were randomized into the following subgroups: During VNS (delivered during presentations of the conditioned stimulus, CS), Between VNS (delivered between CS presentations), Continuous VNS (delivered during the entire extinction session), and Dispersed VNS (delivered at longer inter-stimulation intervals across the extinction session). Sham VNS rats failed to extinguish the conditioned fear response over 5 days of repeated exposure to the CS. Rats that received Between or Dispersed VNS showed modest improvement in conditioned fear at the retention test. During and Continuous VNS groups displayed the greatest reduction in conditioned fear. These findings indicate that delivering VNS paired precisely with CS presentations or continuously throughout extinction promotes the maximum enhancement in extinction learning.