The viviparous sea snakes (Hydrophiinae) comprise ∼90% of living marine reptiles and display many physical and behavioral adaptations for breathing, diving, and achieving osmotic balance in marine habitats. Among the most important innovations found in marine snakes are their paddle-shaped (dorsoventrally expanded) tails, which provide propulsive thrust in the dense aquatic medium. Here, we reconstruct the evolution of caudal paddles in viviparous sea snakes using a dated molecular phylogeny for all major lineages and computed tomography of internal osteological structures. Bayesian ancestral state reconstructions show that extremely large caudal paddles supported by elongated vertebral processes are unlikely to have been present in the most recent common ancestor of extant sea snakes. Instead, these characters appear to have been acquired independently in two highly marine lineages of relatively recent origin. Both the Aipysurus and Hydrophis lineages have elongated neural spines that support the dorsal edge of their large paddles. However, whereas in the Aipysurus lineage the ventral edge of the paddle is supported by elongated haemapophyses, this support is provided by elongated and ventrally directed pleurapophyses in the Hydrophis lineage. Three semi-marine lineages (Hydrelaps, Ephalophis, and Parahydrophis) form the sister group to the Hydrophis clade and have small paddles with poorly developed dorsal and ventral supports, consistent with their amphibious lifestyle. Overall, our results suggest that not only are the viviparous hydrophiines the only lineage of marine snakes to have acquired extremely large, skeletally supported caudal paddles but also that this innovation has occurred twice in the group in the past ∼2–6 million years.