Climate change will likely have profound effects on cold-water species of freshwater fishes. As temperatures rise, cold-water fish distributions may shift and contract in response. Predicting the effects of projected stream warming in stream networks is complicated by the generally poor correlation between water temperature and air temperature. Spatial dependencies in stream networks are complex because the geography of stream processes is governed by dimensions of flow direction and network structure. Therefore, forecasting climate-driven range shifts of stream biota has lagged behind similar terrestrial modeling efforts. We predicted climate-induced changes in summer thermal habitat for 3 cold-water fish species—juvenile Chinook salmon, rainbow trout, and bull trout (Oncorhynchus tshawytscha, O. mykiss, and Salvelinus confluentus, respectively)—in the John Day River basin, northwestern United States. We used a spatially explicit statistical model designed to predict water temperature in stream networks on the basis of flow and spatial connectivity. The spatial distribution of stream temperature extremes during summers from 1993 through 2009 was largely governed by solar radiation and interannual extremes of air temperature. For a moderate climate change scenario, estimated declines by 2100 in the volume of habitat for Chinook salmon, rainbow trout, and bull trout were 69–95%, 51–87%, and 86–100%, respectively. Although some restoration strategies may be able to offset these projected effects, such forecasts point to how and where restoration and management efforts might focus.