Teleost fishes vary in their reliance on median and paired fins (MPF) or undulation of the body (BCF) to generate thrust during straight-line, steady swimming. Previous work indicates that swimming mode is associated with different body shapes, though this has never been empirically demonstrated across the diversity of fishes. As the body does not play as active a mechanical role in steady swimming by MPF swimmers, this may relax constraints and spur higher rates of body shape diversification. We test these predictions by measuring the impact of the dominant steady swimming mode on the evolution of body shape across 2,295 marine teleost fishes. Aligning with historical expectations, BCF swimmers exhibit a more elongate, slender body shape, while MPF propulsion is associated with deeper and wider body shapes. However, in contrast to expectations, we find that BCF propulsion is associated with higher morphological diversity and greater variance around trait optima. This surprising result is consistent with the interpretation that stronger functional trade-offs stimulate phenotypic evolution, rather than constrain it.