A spinal cord injury interrupts pathways from the brain and brainstem that project to the lumbar spinal cord, leading to paralysis. Here we show that spatiotemporal epidural electrical stimulation (EES) of the lumbar spinal cord applied during neurorehabilitation (EES) restored walking in nine individuals with chronic spinal cord injury. This recovery involved a reduction in neuronal activity in the lumbar spinal cord of humans during walking. We hypothesized that this unexpected reduction reflects activity-dependent selection of specific neuronal subpopulations that become essential for a patient to walk after spinal cord injury. To identify these putative neurons, we modelled the technological and therapeutic features underlying EES in mice. We applied single-nucleus RNA sequencing and spatial transcriptomics to the spinal cords of these mice to chart a spatially resolved molecular atlas of recovery from paralysis. We then employed cell type and spatial prioritization to identify the neurons involved in the recovery of walking. A single population of excitatory interneurons nested within intermediate laminae emerged. Although these neurons are not required for walking before spinal cord injury, we demonstrate that they are essential for the recovery of walking with EES following spinal cord injury. Augmenting the activity of these neurons phenocopied the recovery of walking enabled by EES, whereas ablating them prevented the recovery of walking that occurs spontaneously after moderate spinal cord injury. We thus identified a recovery-organizing neuronal subpopulation that is necessary and sufficient to regain walking after paralysis. Moreover, our methodology establishes a framework for using molecular cartography to identify the neurons that produce complex behaviours.