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 comes 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. The spatial network structure allows a substantial reduction in the uncertainty associated with paleo-streamflow as one proceeds downstream in the network and the spatial dependence structure increases the information content. Our application to eighteen 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. A comparison with the traditional principal components regression shows that the spatial Bayesian model offers improvements, as downstream gauges are informed by the reconstruction of the upstream gauges, as well as the tree-ring chronologies.