The imminent demise of montane species is a recurrent theme in the climate change literature, particularly for aquatic species that are constrained to networks and elevational rather than latitudinal retreat as temperatures increase. Predictions of widespread species losses, however, have yet to be fulfilled despite decades of climate change, suggesting that trends are much weaker than anticipated and may be too subtle for detection given the widespread use of sparse water temperature datasets or imprecise surrogates like elevation and air temperature. Through application of large water-temperature databases evaluated for sensitivity to historical air-temperature variability and computationally interpolated to provide high-resolution thermal habitat information for a 222,000-km network, we estimate a less dire thermal plight for cold-water species within mountains of the northwestern United States. Stream warming rates and climate velocities were both relatively low for 1968–2011 (average warming rate = 0.101 °C/decade; median velocity = 1.07 km/decade) when air temperatures warmed at 0.21 °C/decade. Many cold-water vertebrate species occurred in a subset of the network characterized by low climate velocities, and three native species of conservation concern occurred in extremely cold, slow velocity environments (0.33–0.48 km/decade). Examination of aggressive warming scenarios indicated that although network climate velocities could increase, they remain low in headwaters because of strong local temperature gradients associated with topographic controls. Better information about changing hydrology and disturbance regimes is needed to complement these results, but rather than being climatic cul-de-sacs, many mountain streams appear poised to be redoubts for cold-water biodiversity this century.