Salamanders and lungfishes are the only sarcopterygians (lobe-finned vertebrates) capable of paired appendage regeneration, regardless of the amputation level. Among actinopterygians (ray-finned fishes), regeneration after amputation at the fin endoskeleton has only been demonstrated in polypterid fishes (Cladistia). Whether this ability evolved independently in sarcopterygians and actinopterygians or has a common origin remains unknown. Here we combine fin regeneration assays and comparative RNA-sequencing (RNA-seq) analysis of Polypterus and axolotl blastemas to provide support for a common origin of paired appendage regeneration in Osteichthyes (bony vertebrates). We show that, in addition to polypterids, regeneration after fin endoskeleton amputation occurs in extant representatives of 2 other nonteleost actinopterygians: the American paddlefish (Chondrostei) and the spotted gar (Holostei). Furthermore, we assessed regeneration in 4 teleost species and show that, with the exception of the blue gourami (Anabantidae), 3 species were capable of regenerating fins after endoskeleton amputation: the white convict and the oscar (Cichlidae), and the goldfish (Cyprinidae). Our comparative RNA-seq analysis of regenerating blastemas of axolotl and Polypterus reveals the activation of common genetic pathways and expression profiles, consistent with a shared genetic program of appendage regeneration. Comparison of RNA-seq data from early Polypterus blastema to single-cell RNA-seq data from axolotl limb bud and limb regeneration stages shows that Polypterus and axolotl share a regeneration-specific genetic program. Collectively, our findings support a deep evolutionary origin of paired appendage regeneration in Osteichthyes and provide an evolutionary framework for studies on the genetic basis of appendage regeneration.