Several studies have documented a global pattern of phenological advancement that is consistent with ongoing climate change. However, the magnitude of these phenological shifts is highly variable across taxa and locations. This variability of phenological responses has been difficult to explain mechanistically. To examine how the evolution of multi-trait cueing strategies could produce variable responses to climate change, we constructed a model in which organisms evolve strategies that integrate multiple environmental cues to inform anticipatory phenological decisions. We simulated the evolution of phenological cueing strategies in multiple environments, using historic climate data from 78 locations in North America and Hawaii to capture features of climatic correlation structures in the real world. Organisms in our model evolved diverse strategies that were spatially autocorrelated across locations on a continental scale, showing that similar strategies tend to evolve in similar climates. Within locations, organisms often evolved a wide range of strategies that showed similar response phenotypes and fitness outcomes under historical conditions. However, these strategies responded differently to novel climatic conditions, with variable fitness consequences. Our model shows how the evolution of phenological cueing strategies can explain observed variation in phenological shifts and unexpected responses to climate change.