The biomechanics of terrestrial legged locomotion has been extensively studied, but underwater legged locomotion is virtually unstudied. On land, animals change gaits as they increase in speed, e.g., from walking to running. These gaits are different in that step-by-step fluctuations in the kinetic and potential energy of the center of mass change from being out of phase in walking to being in phase during running. The transition from walking to running can be interpreted in terms of a dimensionless number, the Froude number, which is a ratio of inertial to gravitational forces. We have developed underwater versions of the Froude number to account for drag, fluid accelerations and buoyancy. We have discovered that sea stars use two gaits that are neither walking nor running, for two different speed ranges. And we have described how the multitude of legs work to develop effective steps. Octopi and crabs show similar oscillating patterns of motion as sea stars. A biomimetic approach based on sea stars is being used by engineers to design underwater soft-bodied robots.