Most spinal cord injuries lead to permanent paralysis in mammals. By contrast, the remarkable regenerative abilities of salamanders enable full functional recovery even from complete spinal cord transections. The molecular differences underlying this evolutionary divergence between mammals and amphibians are poorly understood. We focused on upstream regulators of gene expression as primary entry points into this question. We identified a group of miRNAs that are conserved between the Mexican axolotl salamander and mammals, but show marked cross-species differences in regulation patterns following spinal cord injury. We found that precise post-injury levels of one of these miRNAs (miR-125b) is essential for functional recovery, and guides correct regeneration of axons through the lesion site in a process involving the direct downstream target Sema4D in axolotls. Translating these results to a mammalian model, we increased miR-125b levels in the rat through mimic treatments following spinal cord transection. These treatments down-regulated Sema4D and other glial-scar related genes, and enhanced the animal's functional recovery. Our study identifies a key regulatory molecule conserved between salamander and mammal, and shows that the levels of miR-125b and its target gene Sema4D must be carefully controlled in the right cells at the correct level to promote regeneration. We also show that this molecular component of the salamander's regeneration-permissive environment can be experimentally harnessed to improve treatment outcomes for mammalian spinal cord injuries.