Vagus nerve stimulation (VNS) was shown to reduce seizure frequency in refractory epilepsy patients in two pilot studies. Based on these results, a multicenter, prospectively randomized, parallel, double-blind study of patients with refractory partial seizures was initiated. After a 12-week baseline period, identical vagus nerve stimulators were implanted and patients randomized to either a high or low 14-week VNS treatment paradigm. The primary objective was to demonstrate that high VNS (therapeutic parameters) was more effective in reducing partial seizure frequency than was low VNS (less or noneffective parameters). Patients continued receiving antiepileptic drugs (AEDs) with plasma concentrations held constant throughout the study. We report results of the first 67 patients to exit the 14-week acute phase. After 14 weeks of VNS, 31 patients receiving high VNS experienced a mean seizure frequency percentage reduction of 30.9%, which was statistically significant as compared with the mean seizure frequency percentage reduction of 11.3% in 36 patients receiving low VNS (p = 0.029, t test; p = 0.036, Wilcoxon rank-sum test). In addition to the significant intragroup p-values, mean seizure frequency percentage change reached statistical significance for high VNS (p < 0.001) but not low VNS (p = 0.072) as compared with baseline. Twelve of 31 (38.7%) patients receiving high VNS achieved at least 50% reduction in seizure frequency whereas 7 of 36 (19.4%) patients receiving low VNS experienced at least 50% reduction after 14 weeks. The implant procedure and VNS therapy were well tolerated. Our study confirmed the effectiveness of VNS as treatment for epilepsy patients with refractory partial seizures.