Swimming spermatozoa from diverse organisms often have very similar morphologies, yet different motilities as a result of differences in the flagellar waveforms used for propulsion. The origin of these differences has remained largely unknown. Using high-speed video microscopy and mathematical analysis of flagellar shape dynamics, we quantitatively compare sperm flagellar waveforms from marine invertebrates to humans by means of a novel phylokinematic tree. This new approach revealed that genetically dissimilar sperm can exhibit strikingly similar flagellar waveforms and identifies two dominant flagellar waveforms among the deuterostomes studied here, corresponding to internal and external fertilizers. The phylokinematic tree shows marked discordance from the phylogenetic tree, indicating that physical properties of the fluid environment, more than genetic relatedness, act as an important selective pressure in shaping the evolution of sperm motility. More broadly, this work provides a physical axis to complement morphological and genetic studies to understand evolutionary relationships.