Climate-induced changes in spatial and temporal occurrence of species, as well as species traits such as body size, each have the potential to decouple symbiotic relationships. Past work has focused primarily on direct interactions, particularly those between predators and prey and between plants and pollinators, but studies have rarely demonstrated significant fitness costs to the interacting, coevolving organisms. Here, we demonstrate that changing phenological synchrony in the latter part of the 20th century has different fitness outcomes for the actors within a Batesian mimicry complex, where predators learn to differentiate harmful "model" organisms (stinging Hymenoptera) from harmless "mimics" (hoverflies, Diptera: Syrphidae). We define the mimetic relationships between 2,352 pairs of stinging Hymenoptera and their Syrphidae mimics based on a large-scale citizen science project and demonstrate that there is no relationship between the phenological shifts of models and their mimics. Using computer game-based experiments, we confirm that the fitness of models, mimics, and predators differs among phenological scenarios, creating a phenologically antagonistic system. Finally, we show that climate change is increasing the proportion of mimetic interactions in which models occur first and reducing mimic-first and random patterns of occurrence, potentially leading to complex fitness costs and benefits across all three actors. Our results provide strong evidence for an overlooked example of fitness consequences from changing phenological synchrony.