Vagus nerve stimulation (VNS) is an adjunctive treatment for drug-resistant epilepsy (DRE). However, it is still difficult to predict which patients will respond to VNS treatment and to what extent. We aim to explore the relationship between preoperative heart rate variability (HRV) and VNS outcome. 50 healthy control subjects and 63 DRE patients who had received VNS implants and had at least one year of follow up were included. The preoperative HRV were analyzed by traditional linear methods and heart rhythm complexity analyses with multiscale entropy (MSE). DRE patients had significantly lower complexity indices (CI) as well as traditional linear HRV measurements than healthy controls. We also found that non-responders(0) had significantly lower preoperative CI including Area 1-5, Area 6-15 and Area 6-20 than those in the responders(0) while those of the non-responders(50) had significantly lower RMSSD, pNN50, VLF, LF, HF, TP and LF/HF than the responders(50). In receiver operating characteristic (ROC) curve analysis, Area 6-20 and RMSSD had the greatest discriminatory power for the responders(0) and non-responders(0), responders(50) and non-responders(50), respectively. Our results suggest that preoperative assessment of HRV by linear and MSE analysis can help in predicting VNS outcomes in patients with DRE.