Locomotor strategies in terrestrial tetrapods have evolved from the utilisation of sinusoidal contractions of axial musculature, evident in ancestral fish species, to the reliance on powerful and complex limb muscles to provide propulsive force. Within tetrapods, a hindlimb-dominant locomotor strategy predominates, and its evolution is considered critical for the evident success of the tetrapod transition onto land. Here, we determine the developmental mechanisms of pelvic fin muscle formation in living fish species at critical points within the vertebrate phylogeny and reveal a stepwise modification from a primitive to a more derived mode of pelvic fin muscle formation. A distinct process generates pelvic fin muscle in bony fishes that incorporates both primitive and derived characteristics of vertebrate appendicular muscle formation. We propose that the adoption of the fully derived mode of hindlimb muscle formation from this bimodal character state is an evolutionary innovation that was critical to the success of the tetrapod transition.