Paleohydrologic records can provide unique, long-term perspectives on streamflow variability and hydroclimate for use in water resource planning. Such long-term records can also play a key role in placing both present day events and projected future conditions into a broader context than that offered by instrumental observations. However, relative to other major river basins across the western United States, a paucity of streamflow reconstructions has to date prevented the full application of such paleohydrologic information in the Upper Missouri River Basin. Here we utilize a set of naturalized streamflow records for the Upper Missouri and an expanded network of tree-ring records to reconstruct streamflow at thirty-one gaging locations across the major headwaters of the basin. The reconstructions explain an average of 68% of the variability in the observed streamflow records and extend available records of streamflow back to 886 CE on average. Basin-wide analyses suggest unprecedented hydroclimatic variability over the region during the Medieval period, similar to that observed in the Upper Colorado River Basin, and show considerable synchrony of persistent wet-dry phasing with the Colorado River over the last 1200 years. Streamflow estimates in individual sub-basins of the Upper Missouri demonstrate increased spatial variability in discharge during the Little Ice Age (~1400-1850 CE) compared with the Medieval Climate Anomaly (~800-1400 CE). The network of streamflow reconstructions presented here fills a major geographical void in paleohydrologic understanding and now allows for a long-term assessment of hydrological variability over the majority of the western U.S.