We combine large observed data sets and dynamically downscaled climate data to explore historic and future (2050–2069) stream temperature changes over the topographically diverse Greater Yellowstone Ecosystem (elevation range = 824–4017 m). We link future stream temperatures with fish growth models to investigate how changing thermal regimes could influence the future distribution and persistence of native Yellowstone cutthroat trout (YCT) and competing invasive species. We find that stream temperatures during the recent decade (2000–2009) surpass the anomalously warm period of the 1930s. Climate simulations indicate air temperatures will warm by 1 °C to >3 °C over the Greater Yellowstone by mid-21st century, resulting in concomitant increases in 2050–2069 peak stream temperatures and protracted periods of warming from May to September (MJJAS). Projected changes in thermal regimes during the MJJAS growing season modify the trajectories of daily growth rates at all elevations with pronounced growth during early and late summer. For high-elevation populations, we find considerable increases in fish body mass attributable both to warming of cold-water temperatures and to extended growing seasons. During peak July to August warming, mid-21st century temperatures will cause periods of increased thermal stress, rendering some low-elevation streams less suitable for YCT. The majority (80%) of sites currently inhabited by YCT, however, display minimal loss (<10%) or positive changes in total body mass by midcentury; we attribute this response to the fact that many low-elevation populations of YCT have already been extirpated by historical changes in land use and invasions of non-native species. Our results further suggest that benefits to YCT populations due to warmer stream temperatures at currently cold sites could be offset by the interspecific effects of corresponding growth of sympatric, non-native species, underscoring the importance of developing climate adaptation strategies that reduce limiting factors such as non-native species and habitat degradation.