Severe spinal cord contusions interrupt nearly all brain projections to lumbar circuits producing leg movement. Failure of these projections to reorganize leads to permanent paralysis. Here we modeled these injuries in rodents. A severe contusion abolished all motor cortex projections below injury. However, the motor cortex immediately regained adaptive control over the paralyzed legs during electrochemical neuromodulation of lumbar circuits. Glutamatergic reticulospinal neurons with residual projections below the injury relayed the cortical command downstream. Gravity-assisted rehabilitation enabled by the neuromodulation therapy reinforced these reticulospinal projections, rerouting cortical information through this pathway. This circuit reorganization mediated a motor cortex-dependent recovery of natural walking and swimming without requiring neuromodulation. Cortico-reticulo-spinal circuit reorganization may also improve recovery in humans.