The Nubian Sandstone Aquifer System (NSAS) is made up of three major sub-basins: Kufra, Dakhla, and the N. Sudan Platform. It is one of the world’s largest groundwater systems. The aquifer’s hydrologic setting, connectivity of its sub-basins, and groundwater flow across these sub-basins are currently unclear. To address these issues, we used a combined approach that included: (1) a regionally calibrated groundwater flow model that mimics early (>10,000 years) steady-state conditions under wet climatic periods and later (<10,000 years BP–1960; 1960–2010) transient conditions under arid climatic periods; and (2) groundwater ages (36Cl, 81Kr) and isotopic (18O, 2H) data. The NSAS was recharged on a regional scale in previous wet climatic periods; however, in dry periods, its outcrops are still receiving local modest recharge. A progressive increase in 36Cl groundwater ages was found along groundwater flow directions and along structures that are sub-parallel to the flow direction. The NE–SW Pelusium mega shear zone is a preferential groundwater flow conduit from the Kufra to the Dakhla sub-basin. The south-to-north groundwater flow is hampered by the Uweinat–Aswan basement uplift. The findings provide useful information about the best ways to use the NSAS.