Impending changes in climate will interact with other stressors to threaten aquatic ecosystems and their biota. Native Colorado River cutthroat trout (CRCT; Oncorhynchus clarkii pleuriticus) are now relegated to 309 isolated high-elevation (>1700 m) headwater stream fragments in the Upper Colorado River Basin, owing to past nonnative trout invasions and habitat loss. Predicted changes in climate (i.e., temperature and precipitation) and resulting changes in stochastic physical disturbances (i.e., wildfire, debris flow, and channel drying and freezing) could further threaten the remaining CRCT populations. We developed an empirical model to predict stream temperatures at the fragment scale from downscaled climate projections along with geomorphic and landscape variables. We coupled these spatially explicit predictions of stream temperature with a Bayesian Network (BN) model that integrates stochastic risks from fragmentation to project persistence of CRCT populations across the upper Colorado River basin to 2040 and 2080. Overall, none of the populations are at risk from acute mortality resulting from high temperatures during the warmest summer period. In contrast, only 37% of populations have a greater than or equal to 90% chance of persistence for 70 years (similar to the typical benchmark for conservation), primarily owing to fragmentation. Populations in short stream fragments <7 km long, and those at the lowest elevations, are at the highest risk of extirpation. Therefore, interactions of stochastic disturbances with fragmentation are projected to be greater threats than warming for CRCT populations. The reason for this paradox is that past nonnative trout invasions and habitat loss have restricted most CRCT populations to high-elevation stream fragments that are buffered from the potential consequences of warming, but at risk of extirpation from stochastic events. The greatest conservation need is for management to increase fragment lengths to forestall these risks.