Acquisition of new ecological opportunities is a major driver of adaptation and species diversification [1–4]. However, how groups of organisms expand their habitat range is often unclear [3]. We study the Gerromorpha, a monophyletic group of heteropteran insects that occupy a large variety of water surface-associated niches, from small puddles to open oceans [5, 6]. Due to constraints related to fluid dynamics [7–9] and exposure to predation [5, 10], we hypothesize that selection will favor high speed of locomotion in the Gerromorpha that occupy water-air interface niches relative to the ancestral terrestrial life style. Through biomechanical assays and phylogenetic reconstruction, we show that only species that occupy water surface niches can generate high maximum speeds. Basally branching lineages with ancestral mode of locomotion, consisting of tripod gait, achieved increased speed on the water through increasing midleg length, stroke amplitude, and stroke frequency. Derived lineages evolved rowing as a novel mode of locomotion through simultaneous sculling motion almost exclusively of the midlegs. We demonstrate that this change in locomotory behavior significantly reduced the requirement for high stroke frequency and energy expenditure. Furthermore, we show how the evolution of rowing, by reducing stroke frequency, may have eliminated the constraint on body size, which may explain the evolution of larger Gerromorpha. This correlation between the diversity in locomotion behaviors and niche specialization suggests that changes in morphology and behavior may facilitate the invasion and diversification in novel environments.