European continental shelf seas have experienced intense warming over the past 30 years. In the North Sea, fish have been comprehensively monitored throughout this period and resulting data provide a unique record of changes in distribution and abundance in response to climate change. We use these data to demonstrate the remarkable power of generalized additive models (GAMs), trained on data earlier in the time series, to reliably predict trends in distribution and abundance in later years. Then, challenging process-based models that predict substantial and ongoing poleward shifts of cold-water species, we find that GAMs coupled with climate projections predict future distributions of demersal (bottom-dwelling) fish species over the next 50 years will be strongly constrained by availability of habitat of suitable depth. This will lead to pronounced changes in community structure, species interactions and commercial fisheries, unless individual acclimation or population-level evolutionary adaptations enable fish to tolerate warmer conditions or move to previously uninhabitable locations.