Organisms are expected to adapt or move in response to climate change, but observed distribution shifts span a wide range of directions and rates. Explanations often emphasize biological distinctions among species, but general mechanisms have been elusive. We tested an alternative hypothesis: that differences in climate velocity-the rate and direction that climate shifts across the landscape-can explain observed species shifts. We compiled a database of coastal surveys around North America from 1968 to 2011, sampling 128 million individuals across 360 marine taxa. Climate velocity explained the magnitude and direction of shifts in latitude and depth much more effectively than did species characteristics. Our results demonstrate that marine species shift at different rates and directions because they closely track the complex mosaic of local climate velocities.