Anthropogenic climate change is widely expected to drive species extinct by hampering individual survival and reproduction, by reducing the amount and accessibility of suitable habitat, or by eliminating other organisms that are essential to the species in question. Less well appreciated is the likelihood that climate change will directly disrupt or eliminate mutually beneficial (mutualistic) ecological interactions between species even before extinctions occur. We explored the potential disruption of a ubiquitous mutualistic interaction of terrestrial habitats, that between plants and their animal pollinators, via climate change. We used a highly resolved empirical network of interactions between 1420 pollinator and 429 plant species to simulate consequences of the phenological shifts that can be expected with a doubling of atmospheric CO2. Depending on model assumptions, phenological shifts reduced the floral resources available to 17–50% of all pollinator species, causing as much as half of the ancestral activity period of the animals to fall at times when no food plants were available. Reduced overlap between plants and pollinators also decreased diet breadth of the pollinators. The predicted result of these disruptions is the extinction of pollinators, plants and their crucial interactions.