A Bayesian model that uses the spatial dependence induced by the river network topology and the leading principal components of regional tree ring chronologies for paleo‐streamflow reconstruction is presented. In any river basin, a convergent, dendritic network of tributaries come together to form the main stem of a river. Consequently, it is natural to think of a spatial Markov process that recognizes this topological structure to develop a spatially consistent basin‐scale streamflow reconstruction model that uses the information in streamflow and tree ring chronology data to inform the reconstructed flows, while maintaining the space‐time correlation structure of flows that is critical for water resource assessments and management. Given historical data from multiple streamflow gauges along a river, their tributaries in a watershed, and regional tree ring chronologies, the model is fit and used to simultaneously reconstruct the full network of paleo‐streamflow at all gauges in the basin progressing upstream to downstream along the river. Our application to 18 streamflow gauges in the Upper Missouri River Basin shows that the mean adjusted R2 for the basin is approximately 0.5 with good overall cross‐validated skill as measured by five different skill metrics. The spatial network structure produced a substantial reduction in the uncertainty associated with paleo‐streamflow as one proceeds downstream in the network aggregating information from upstream gauges and tree ring chronologies. Uncertainty was reduced by more than 50% at six gauges, between 6% and 50% at one gauge, and by less than 5% at the remaining 11 gauges when compared with the traditional principal component regression reconstruction model.