Salamanders, frog tadpoles and diverse lizards have the remarkable ability to regenerate tails. Palaeontological data suggest that this capacity is plesiomorphic, yet when the developmental and genetic architecture of tail regeneration arose is poorly understood. Here, we show morphological and molecular hallmarks of tetrapod tail regeneration in the West African lungfish Protopterus annectens, a living representative of the sister group of tetrapods. As in salamanders, lungfish tail regeneration occurs via the formation of a proliferative blastema and restores original structures, including muscle, skeleton and spinal cord. In contrast with lizards and similar to salamanders and frogs, lungfish regenerate spinal cord neurons and reconstitute dorsoventral patterning of the tail. Similar to salamander and frog tadpoles, Shh is required for lungfish tail regeneration. Through RNA-seq analysis of uninjured and regenerating tail blastema, we show that the genetic programme deployed during lungfish tail regeneration maintains extensive overlap with that of tetrapods, with the upregulation of genes and signalling pathways previously implicated in amphibian and lizard tail regeneration. Furthermore, the lungfish tail blastema showed marked upregulation of genes encoding post-transcriptional RNA processing components and transposon-derived genes. Our results show that the developmental processes and genetic programme of tetrapod tail regeneration were present at least near the base of the sarcopterygian clade and establish the lungfish as a valuable research system for regenerative biology.