GRACE Terrestrial Water Storage (TWS) provides unique and unprecedented perspectives about freshwater availability and change globally. However, GRACE-TWS records are relatively short for long-term hydroclimatic variability studies, dating back to April 2002. In this paper, we made use of Noah Land Surface Model (LSM), and El Niño-Southern Oscillation (ENSO) data in an autoregressive model with exogenous variables (ARX) to reconstruct a 66-year record of TWS for nine major transboundary river basins (TRBs) in Africa. Model performance was evaluated using standard indicators, including the Nash Sutcliffe Efficiency criteria, cumulative density frequency, standardized residuals plots, and model uncertainty bounds. Temporally, the reconstruction results were evaluated for trend, cycles, and mode of variability against ancillary data from the WaterGAP Model (WGHM-TWS) and GPCC-based precipitation anomalies. The temporal pattern reveals good agreement between the reconstructed TWS, WGHM-TWS, and GPCC, (p-value < 0.0001). The reconstructed TWS suggests a significant declining trend across the northern and central TRBs since 1951, while the southern basins show an insignificant trend. The mode of variability analysis indicates short storage periodicity of four to sixteen-month in the northern basins, while strong intra-annual variability in the central and southern basins. The long-term TWS records provide additional support to Africa's water resources research on hydroclimatic variability and change in shared transboundary water basins.