Species vulnerability to climate change depends in part on their capacity to evolve in response to increasing heat. Within terrestrial ectotherms, heat tolerance generally corresponds weakly to current climates, which has led many to conclude that this trait is evolutionarily constrained. However, most studies have not accounted for the role of microclimates, potentially obscuring signals of local adaptation. We examined heat tolerance in 95 species of wild bees that varied in nesting behaviour across the latitudinal extent of Australia. Species nest (ground, wooden cavities, or plant stems) micro-climate temperatures predicted heat tolerance evolution, where stem nesters evolved the highest heat tolerances, and ground nesters evolved the lowest heat tolerances due to their ability to evade extreme heat. A moderate level of phylogenetic inertia in heat tolerance was explained by patterns of related species sharing nesting behaviours. This indicated repeated adaptive evolution of similar heat tolerances, rather than strong evolutionary constraints on heat tolerance. Finally, incorporating nesting behaviour into assessments of climate change vulnerability changed the rank order of which species were most at risk. This underscores the need to understand what drives the evolution of heat tolerance across species to better identify the taxa most at risk to climate change.