Climate change can affect organisms both directly via physiological stress and indirectly via changing relationships among species. However, we do not fully understand how changing interspecific relationships contribute to community- and ecosystem-level responses to environmental forcing. I used experiments and spatial and temporal comparisons to demonstrate that warming substantially reduces predator-free space on rocky shores. The vertical extent of mussel beds decreased by 51% in 52 years, and reproductive populations of mussels disappeared at several sites. Prey species were able to occupy a hot, extralimital site if predation pressure was experimentally reduced, and local species richness more than doubled as a result. These results suggest that anthropogenic climate change can alter interspecific interactions and produce unexpected changes in species distributions, community structure, and diversity.