Rapid climate changes are currently driving substantial reorganizations of marine ecosystems around the world. A key question is how these changes will alter the provision of ecosystem services from the ocean, particularly from fisheries. To answer this question, we need to understand not only the ecological dynamics of marine systems, but also human adaptation and feedbacks between humans and the rest of the natural world. In this review, we outline what we have learned from research primarily in continental shelf ecosystems and fishing communities of North America. Key findings are that marine animals are highly sensitive to warming and are responding quickly to changes in water temperature, and that such changes are often happening faster than similar processes on land. Changes in species distributions and productivity are having substantial impacts on fisheries, including through changing catch compositions and longer distances traveled for fishing trips. Conflicts over access to fisheries have also emerged as species distributions are no longer aligned with regulations or catch allocations. These changes in the coupled natural-human system have reduced the value of ecosystem services from some fisheries and risk doing so even more in the future. Going forward, substantial opportunities for more effective fisheries management and operations, marine conservation, and marine spatial planning are likely possible through greater consideration of climate information over time-scales from years to decades.