By influencing water tables of saline aquifers, multiyear dry or wet periods can significantly delay or accelerate dryland salinity, but this effect remains poorly quantified at the large river basin scale. The Gravity and Climate Recovery Experiment (GRACE) satellite measures changes in the total water storage of river systems, providing a unique opportunity for better understanding connections between stream salinity and changes in catchment water storages at the large river basin scale. Here, we quantified the role of GRACE total water storage anomalies (TWSA) in stream salinity variability across Australia’s Murray-Darling Basin (∼1 million km2), while also accounting for streamflow and rainfall. We used the MERRA-2 global land surface model to i) place our findings in the context of the longer-term hydroclimatology (1980-present) and ii) to decompose TWSA into groundwater storage as an alternative driver variable. Multivariate time series regression models (generalized additive mixed models or GAMM) showed that the driver variables could explain 20–50% of the variability in stream salinity across 8 sub-catchments in the Murray Darling Basin. TWSA commonly explained as much variability as streamflow, while groundwater storage and TWSA had very similar explanatory power and rainfall only negligible contributions. The 2000–2009 Millennium Drought and the subsequent La Nina Floods had a predominantly decelerating and accelerating effect on stream salinity respectively and these trends were partially explained by trends in TWSA. Our study illustrates that GRACE can be a useful addition for monitoring and modeling dryland salinity over large river basins.