Water striders Gerridae are insects of characteristic length 1 cm and weight 10 dynes that reside on the surface of ponds, rivers, and the open ocean. Their weight is supported by the surface tension force generated by curvature of the free surface, and they propel themselves by driving their central pair of hydrophobic legs in a sculling motion. Previous investigators have assumed that the hydrodynamic propulsion of the water strider relies on momentum transfer by surface waves. This assumption leads to Denny's paradox: infant water striders, whose legs are too slow to generate waves, should be incapable of propelling themselves along the surface. We here resolve this paradox through reporting the results of high-speed video and particle-tracking studies. Experiments reveal that the strider transfers momentum to the underlying fluid not primarily through capillary waves, but rather through hemispherical vortices shed by its driving legs. This insight guided us in constructing a self-contained mechanical water strider whose means of propulsion is analogous to that of its natural counterpart.