Paired vagus nerve stimulation (VNS) has emerged as a promising strategy to potentiate recovery after neurological injury. This approach, which combines short bursts of electrical stimulation of the vagus nerve with rehabilitation exercises, received approval from the US Food and Drug Aministration in 2021 as the first neuromodulation-based therapy for chronic stroke. Because this treatment is increasingly implemented in clinical practice, there is a need to take stock of what we know about this approach and what we have yet to learn. Here, we provide a survey on the foundational basis of VNS therapy for stroke and offer insight into the mechanisms that underlie potentiated recovery, focusing on the principles of neuromodulatory reinforcement. We discuss the current state of observations regarding synaptic reorganization in motor networks that are enhanced by VNS, and we propose other prospective loci of neuromodulation that should be evaluated in the future. Finally, we highlight the future opportunities and challenges to be faced as this approach is increasingly translated to clinical use. Collectively, a clearer understanding of the mechanistic basis of VNS therapy may reveal ways to maximize its benefits.