Stream water temperature plays a significant role in aquatic ecosystems where it controls many important biological and physical processes. Reliable estimates of water temperature at the daily time step are critical in managing water resources. We developed a parsimonious piecewise Bayesian model for estimating daily stream water temperatures that account for temporal autocorrelation and both linear and nonlinear relationships with air temperature and discharge. The model was tested at 8 climatically different basins of the USA and at 34 sites within the mountainous Boise River Basin (Idaho, USA). The results show that the proposed model is robust with an average root mean square error of 1.25 °C and Nash-Sutcliffe coefficient of 0.92 over a 2-year period. Our approach can be used to predict historic daily stream water temperatures in any location using observed daily stream temperature and regional air temperature data.