We use monthly measurements of time-variable gravity from the GRACE (Gravity Recovery and Climate Experiment) satellite mission to quantify changes in terrestrial water storage (TWS) in the Lena river basin, Eurasia, during the period April 2002 to September 2010. We estimate a TWS increase of 32 ± 10 km3/yr for the entire basin, equivalent to an increase in water thickness of 1.3 ± 0.4 cm/yr over a basin of 2.4 million km2. We compare TWS estimates from GRACE with time series of precipitation (P) minus evapotranspiration (ET) from ERA-Interim reanalysis minus observational river discharge (R). We find an excellent agreement in annual and inter-annual variability between the two time series. Furthermore, we find that a bias of −20 ± 10% in P-ET is sufficient to effectively close the water budget with GRACE. When we account for this bias, the time series of cumulative TWS from GRACE and climatological data agree to within ±3.8 cm of water thickness, or ±9% of the mean annual P. The TWS increase is not uniform across the river basin and exhibits a peak, over an area of 502,400 km2, centered at 118.5°E, 62.5°N, and underlain by discontinuous permafrost. In this region, we attribute the observed TWS increase of 68 ± 19 km3 to an increase in subsurface water storage. This large subsurface water signal will have a significant impact on the terrestrial hydrology of the region, including increased baseflow and alteration of seasonal runoff.