Paleohydrologic records provide a valuable perspective on the variability of streamflow and hydroclimate that is critical for water resource planning and placing present day and future conditions into a long-term context. Until now, key insights gained from streamflow reconstructions in the other river basins across the Western U.S. been lacking in the Upper Missouri River Basin due to a lack of extended streamflow records. Here we utilize a new database of naturalized streamflow records for the Upper Missouri and an expanded network of tree-ring records from the region to reconstruct streamflow at 31 gaging locations across the major Mountain Headwaters of the United States’ largest river basin. The database also includes an Upper Missouri Basin Basin composite record of streamflow that is not specific to any streamgage location, but rather summarizes streamflow variability across all the major gaging locations in the Upper Missouri River. The reconstructions explain an average of 68% of the variability in the observed streamflow records and extend records of streamflow to C.E. 886 on average. The network of streamflow reconstructions presented here fills a major geographical void in paleohydrologic understanding and provides important data resources to water managers balancing increasing water demands for hydropower, irrigation, navigation, and ecological resources with increasing flood risk in the basin.