Chemotaxis underpins important ecological processes in marine bacteria, from the association with primary producers to the colonization of particles and hosts. Marine bacteria often swim with a single flagellum at high speeds, alternating “runs” with either 180° reversals or ∼90° “flicks,” the latter resulting from a buckling instability of the flagellum. These adaptations diverge from Escherichia coli’s classic run-and-tumble motility, yet how they relate to the strong and rapid chemotaxis characteristic of marine bacteria has remained unknown. We investigated the relationship between swimming speed, run–reverse–flick motility, and high-performance chemotaxis by tracking thousands of Vibrio alginolyticus cells in microfluidic gradients. At odds with current chemotaxis models, we found that chemotactic precision—the strength of accumulation of cells at the peak of a gradient—is swimming-speed dependent in V. alginolyticus. Faster cells accumulate twofold more tightly by chemotaxis compared with slower cells, attaining an advantage in the exploitation of a resource additional to that of faster gradient climbing. Trajectory analysis and an agent-based mathematical model revealed that this unexpected advantage originates from a speed dependence of reorientation frequency and flicking, which were higher for faster cells, and was compounded by chemokinesis, an increase in speed with resource concentration. The absence of any one of these adaptations led to a 65–70% reduction in the population-level resource exposure. These findings indicate that, contrary to what occurs in E. coli, swimming speed can be a fundamental determinant of the gradient-seeking capabilities of marine bacteria, and suggest a new model of bacterial chemotaxis.