Warmer springs advance many phenological events, including flowering time in plants and the flight-time of insects . Pollination by insects, an ecosystem service of immense economic and conservation importance , depends on synchrony between insect activity and flowering time. If plants and their pollinators show different phenological responses to climate warming, pollination could fail. Information about the effects of warming on specific plant/insect mutualisms is difficult to obtain from complex pollination networks . In contrast, the extraordinarily specific deceptions evolved by orchids  that attract a very narrow range of pollinators allow direct examination of the potential for climatic warming to disrupt synchrony. Here we show that a sexually deceptive orchid and the solitary bee on which it depends for pollination will diverge in phenology with increasing spring temperature. Male bees inadvertently pollinate the orchid flowers during pseudocopulation. Analysis of museum specimens (1893-2007) and recent field-based records (1975-2009) showed that flight date of the solitary bee Andrena nigroaenea is advanced more by higher temperatures than flowering date in the deceptive orchid Ophrys sphegodes. Male bees emerged slightly earlier than females, which attract male copulatory attentions away from the deceptive flowers. Warming by as little as 2° C increased both the probability of male flight, and the proportion of females flying in the bee population, before orchid flowering; this would reduce the frequency of pseudocopulation and thus lower pollination success rate in the orchid. Our results demonstrate a significant potential for coevolved plant-pollinator relationships to be disrupted by climatic warming.