Many vertebrates have the amazing ability to regenerate all or portions of appendages including limbs, tails, fins, and digits. Unfortunately, our understanding of the cellular and molecular basis of appendage regeneration is severely lacking. However, recent technological advances that facilitate the tracking of cell lineages in vivo through space and time are allowing us to address the unknowns of regeneration, such as characterizing the cells that contribute to regeneration and identifying the tissues these cells differentiate into during regeneration. Here, we describe the experiments and the surprisingly uniform results that have emerged across diverse vertebrate species when specific cell lineages have been tracked during vertebrate appendage regeneration. These investigations show that vertebrates, from zebrafish to salamanders to mammals, utilize a limited amount of cellular plasticity to regenerate missing appendages. The universal approach to appendage regeneration is not to generate pluripotent cells that then differentiate into the new organ, but instead to generate lineage-restricted cells that are propagated in a progenitor-like state. Lessons learned from these natural cases of complex tissue regeneration might inform regenerative medicine on the best approach for re-growing complex tissues.