Simulations of stream temperatures showed a wide range of future thermal regimes under a warming climate — from 2.9°C warmer to 7.6°C cooler than current conditions — depending primarily on shade from riparian vegetation. We used the stream temperature model, Heat Source, to analyze a 37-km study segment of the upper Middle Fork John Day River, located in northeast Oregon, USA. We developed alternative future scenarios based on downscaled projections from climate change models and the composition and structure of native riparian forests. We examined 36 scenarios combining future changes in air temperature (DTair = 0°C, +2°C, and +4°C), stream discharge (DQ = 30%, 0%, and +30%), and riparian vegetation (post-wildfire with 7% shade, current vegetation with 19% shade, a young-open forest with 34% shade, and a mature riparian forest with 79% effective shade). Shade from riparian vegetation had the largest influence on stream temperatures, changing the seven-day average daily maximum temperature (7DADM) from +1°C to 7°C. In comparison, the 7DADM increased by 1.4°C with a 4°C increase in air temperature and by 0.7°C with a 30% change in discharge. Many streams throughout the interior western United States have been altered in ways that have substantially reduced shade. The effect of restoring shade could result in future stream temperatures that are colder than today, even under a warmer climate with substantially lower late-summer streamflow.