Climate change places considerable stress on riverine ecosystems by altering flow regimes and increasing water temperature. This study evaluated how water temperature increases under climate change scenarios will affect stream invertebrates in pristine headwater streams. The studied headwater-stream sites were distributed within a temperate catchment of Japan and had similar hydraulic-geographical conditions, but were subject to varying temperature conditions due to altitudinal differences (100 to 850 m). We adopted eight general circulation models (GCMs) to project air temperature under conservative (RCP2.6), intermediate (RCP4.5), and extreme climate scenarios (RCP8.5) during the near (2031–2050) and far (2081–2100) future. Using the water temperature of headwater streams computed by a distributed hydrological-thermal model as a predictor variable, we projected the population density of stream invertebrates in the future scenarios based on generalized linear models. The mean decrease in the temporally averaged population density of Plecoptera was 61.3% among the GCMs, even under RCP2.6 in the near future, whereas density deteriorated even further (90.7%) under RCP8.5 in the far future. Trichoptera density was also projected to greatly deteriorate under RCP8.5 in the far future. We defined taxa that exhibited temperature-sensitive declines under climate change as cold stenotherms and found that most Plecoptera taxa were cold stenotherms in comparison to other orders. Specifically, the taxonomic families that only distribute in Palearctic realm (e.g., Megarcys ochracea and Scopura longa) were selectively assigned, suggesting that Plecoptera family with its restricted distribution in the Palearctic might be a sensitive indicator of climate change. Plecoptera and Trichoptera populations in the headwaters are expected/anticipated to decrease over the considerable geographical range of the catchment, even under the RCP2.6 in the near future. Given headwater invertebrates play important roles in streams, such as contributing to watershed productivity, our results provide useful information for managing streams at the catchment-level.