Vagus nerve stimulation (VNS) is an approved therapy for treatment of epilepsy and depression. While also shown to be promising in several preclinical and clinical studies to treat cardiovascular diseases, optimal therapeutic stimulation paradigms are still under investigation. Traditionally, parameters such as frequency, current, and duty cycle are used to adjust the efficacy of VNS therapy. This study explored the effect of novel stochastic VNS (S-VNS) on acute heart rate (HR) dynamics. The effect of S-VNS was evaluated in Sprague Dawley rats by comparing the acute HR and HR variability (HRV) responses to standard, periodic VNS (P-VNS) across different frequencies (FREQs, 10–30 Hz). Our results demonstrate that both S-VNS and P-VNS produced negative chronotropic effects in a FREQ-dependent manner with S-VNS inducing a significantly smaller drop in HR at 10 Hz and 20 Hz compared to P-VNS (p<0.05). S-VNS demonstrated a FREQ-dependent drop in the SD1/SD2 ratio, a measure of HRV, which was absent in P-VNS, suggesting that S-VNS may acutely modulate the nonlinear relationship between short- and long-term HRV. In conclusion, S-VNS is a novel stimulation procedure that may provide different physiological outcomes from standard P-VNS, as indicated by our analysis of HR dynamics. Our study provides a rationale for further detailed investigations into the therapeutic potential of S-VNS as a novel neuromodulation technique.