Species vulnerability to climate change involves an interaction between the magnitude of change (exposure) and a species’ tolerance to change. We evaluated fish species vulnerability to predicted stream temperature increases by examining warming tolerances across the Wyoming fish assemblage. Warming tolerance combines stream temperature with a thermal tolerance metric to estimate how much warming beyond current conditions a species can withstand. Brown trout, rainbow trout, and burbot had the lowest warming tolerances and highest proportion of currently occupied sites that will become unsuitable under predicted temperature increases. These most vulnerable species were coldwater species, but had neither the lowest thermal tolerances, nor would they experience the greatest temperature increases. Our results highlight the importance of considering the interaction of exposure and warming tolerance when predicting climate change vulnerability and demonstrate an approach that can be applied broadly.