Salamanders regenerate appendages via a progenitor pool called the blastema. The cellular mechanisms underlying regeneration of muscle have been much debated but have remained unclear. Here we applied Cre-loxP genetic fate mapping to skeletal muscle during limb regeneration in two salamander species, Notophthalmus viridescens (newt) and Ambystoma mexicanum (axolotl). Remarkably, we found that myofiber dedifferentiation is an integral part of limb regeneration in the newt, but not in axolotl. In the newt, myofiber fragmentation results in proliferating, PAX7(-) mononuclear cells in the blastema that give rise to the skeletal muscle in the new limb. In contrast, myofibers in axolotl do not generate proliferating cells, and do not contribute to newly regenerated muscle; instead, resident PAX7(+) cells provide the regeneration activity. Our results therefore show significant diversity in limb muscle regeneration mechanisms among salamanders and suggest that multiple strategies may be feasible for inducing regeneration in other species, including mammals.