The thermal state of the northern rivers of Russia has significantly changed during the last 30–40 years due to climate warming and changes in water runoff. The purpose of this study is to investigate and analyse these changes, their long-term and spatial patterns. In the northeast Asian part of Russia, including Chukotka, the northern districts of Yakutia and the Magadan Region, the thermal state of rivers is affected by cold climatic conditions, high altitudes, continuous permafrost, aufeis, glacial runoff and groundwater recharge. It is closely related to flow direction and dimension of rivers. The study uses dataset containing observations of river water temperature (mainly from 1955 to 2012/2018) at 231 gauging stations and records of 34 weather stations. The large dataset enabled to create seasonal and monthly air temperature maps, as well as maps of deviation of these parameters from the values of background period. The boundaries of ten altitude-thermal zones were set and for each zone a relationship between temperature and mean catchment height was established. Empirical relationships between water and air temperatures showed the leading role of air temperature in changes in stream temperature. It was found that, despite the huge size of the northeastern region and contrasting natural conditions, noticeable climatic warming (by 1–2°C) has been recorded almost at the same time (since 1988). To the east of the Indigirka River, it has been detected since the mid-1990s. The air temperatures increase in spring and autumn is higher than in summer when the main river heat-flux is generated. The beginning of the first noticeable increase in stream temperatures dates back to the late 1980s. The next time milestones were the mid-late 1990s, the first half of the 2000s (from the Indigirka River to the Anadyr River), the late 2000s–early 2010s (western part of the region). The rivers and territories with positive water temperature anomalies predominate. The average range of anomalies is from ‒0.2 to +1.5°C; extreme values are from ‒0.8 to +2°C. The Arctic rivers, the area at the intersection of the Vilyuy and Olenek river basins, and the rivers to the east of the Kolyma River have maximum positive water temperature anomalies. Observed trends create favorable conditions for the intensification of thermal erosion and an increase in turbidity of river water.