Water temperature affects the biology and ecology of many freshwater species. However, in situ water temperature measurements are not always available due to spatial or temporal gaps in observations. This necessitates the development of methods to accurately predict water temperature from other data sources. We evaluated the importance of different environmental variables in predicting water temperature and developed a water temperature model for use in fluvial environments. We used linear mixed effects models that incorporated different combinations of air temperature, stream flow and catchment characteristic variables to predict daily water temperatures of rivers and streams across southeastern Australia. Air temperature integrated over the last seven days, in conjunction with elevation, were excellent predictors of water temperature. However, stream flow did not significantly improve model predictions. Air temperature explained the most variation in water temperature while elevation also improved model predictions. We hypothesise that elevation captures aspects of land use that may affect heat exchange. Our approach demonstrates that water temperature can be readily modelled using elevation and air temperature across large spatial and temporal scales. Our work provides an easily implementable method to help fill spatial and temporal gaps in monitoring networks.