The Nile River Basin (NRB) is facing extreme pressure on its water resources due to an alarmingly increasing population that is extremely vulnerable in aspects of irrigation and hydropower. The NRB ascends itself to remotely sensed approaches with high resolution of spatial and temporal coverage as disparate to ground-based in-situ observations due to its size and limited access from basin countries. The Gravity Recovery and Climate Experiment (GRACE) allow a unique opportunity to investigate the changes in key components of Terrestrial Water Storage (TWS). Differences in tuning parameters and processing strategies result in GRACE TWS solutions with regionally specific variations and error patterns. We explored the spatiotemporal changes of the TWS time series, trend, uncertainties, and signal-to-noise ratio (SNR) among different GRACE TWS. We had also investigated the key terrestrial water storage components (surface water, soil moisture, and groundwater storage changes). The results show that the uncertainty of GRACE spherical harmonic (SH) solutions are higher than the mass concentration (mascon) over the NRB, and the Center for Space Research-mascons (CSR-M) noted the first best performance. Substantially, significant long-term (2003–2017) negative groundwater and soil moisture trend demonstrates a potential depletion over NRB. Despite an increase in precipitation and TWS time series, the rate of decline noted to increase rapidly from 2008, thus indicating the possibility of human-induced change ( e.g., for irrigation purposes). Thus, the result of this study provides a guiding principle for future studies in TWS change-related hydro-climatic change over NRB and similar basins.