Stream water temperature is changing around the globe. However, there remains relatively few studies quantifying this phenomenon due to a lack of suitable long-term datasets coupled with the challenges of analysing long-term datasets that are typically characterised by sparse geographic coverage, changing site locations and infrequent sampling. We describe an approach to address these challenges using spatio-temporal analysis of an existing long-term network for the Greater Melbourne region in south-east Australia. The challenges of working with the changing temporal resolution of sampling that is characteristic of long-term stream water quality monitoring networks have been overcome through calculation of temperature anomalies to identify long-term and seasonally changing warming trends. Further insight has been gained through the development of statistical models based on the physical mechanisms that influence stream temperature. These models identify the relative influence that different physical processes have on stream temperature for this region, the influence those processes have on water temperature changes and where (and when) they occur in the catchment. The models can also be used to infer how homogenous or heterogeneous changes in water temperature are likely to be over the catchment and identify regions at threat of greater warming. Identifying the key processes driving changes in water temperature in the region allows for assessment of the suitability of the existing network for identifying future changes, identification of gaps in the current sampling strategy or areas of redundant sampling, and for optimisation of future sampling strategies.