Mosasaurs (family Mosasauridae) are a diverse group of secondarily aquatic lizards that radiated into marine environments during the Late Cretaceous (98-65 million years ago). For the most part, they have been considered to be simple anguilliform swimmers--i.e., their propulsive force was generated by means of lateral undulations incorporating the greater part of the body--with unremarkable, dorsoventrally narrow tails and long, lizard-like bodies. Convergence with the specialized fusiform body shape and inferred carangiform locomotory style (in which only a portion of the posterior body participates in the thrust-producing flexure) of ichthyosaurs and metriorhynchid crocodyliform reptiles, along with cetaceans, has so far only been recognized in Plotosaurus, the most highly derived member of the Mosasauridae. Here we report on an exceptionally complete specimen (LACM 128319) of the moderately derived genus Platecarpus that preserves soft tissues and anatomical details (e.g., large portions of integument, a partial body outline, putative skin color markings, a downturned tail, branching bronchial tubes, and probable visceral traces) to an extent that has never been seen previously in any mosasaur. Our study demonstrates that a streamlined body plan and crescent-shaped caudal fin were already well established in Platecarpus, a taxon that preceded Plotosaurus by 20 million years. These new data expand our understanding of convergent evolution among marine reptiles, and provide insights into their evolution's tempo and mode.