Background and Purpose- We assessed safety, feasibility, and potential effects of vagus nerve stimulation (VNS) paired with rehabilitation for improving arm function after chronic stroke. Methods- We performed a randomized, multisite, double-blinded, sham-controlled pilot study. All participants were implanted with a VNS device and received 6-week in-clinic rehabilitation followed by a home exercise program. Randomization was to active VNS (n=8) or control VNS (n=9) paired with rehabilitation. Outcomes were assessed at days 1, 30, and 90 post-completion of in-clinic therapy. Results- All participants completed the course of therapy. There were 3 serious adverse events related to surgery. Average FMA-UE scores increased 7.6 with active VNS and 5.3 points with control at day 1 post-in-clinic therapy (difference, 2.3 points; CI, -1.8 to 6.4; P=0.20). At day 90, mean scores increased 9.5 points from baseline with active VNS, and the control scores improved by 3.8 (difference, 5.7 points; CI, -1.4 to 11.5; P=0.055). The clinically meaningful response rate of FMA-UE at day 90 was 88% with active VNS and 33% with control VNS ( P<0.05). Conclusions- VNS paired with rehabilitation was acceptably safe and feasible in participants with upper limb motor deficit after chronic ischemic stroke. A pivotal study of this therapy is justified. Clinical Trial Registration- URL: https://www.clinicaltrials.gov . Unique identifier: NCT02243020.