The Barents Sea is subject to ongoing postglacial uplift since the melting of the Weichselian ice sheet that covered it. The regional ice sheet thickness history is not well known because there is only data at the periphery due to the locations of Franz Joseph Land, Svalbard, and Novaya Zemlya surrounding this paleo ice sheet. We show that the linear trend in the gravity rate derived from a decade of observations from the Gravity Recovery and Climate Experiment (GRACE) satellite mission can constrain the volume of the ice sheet after correcting for current ice melt, hydrology, and far-field gravitational effects. Regional ice-loading models based on new geologically inferred ice margin chronologies show a significantly better fit to the GRACE data than that of ICE-5G. The regional ice models contain less ice in the Barents Sea than present in ICE-5G (5–6.3?m equivalent sea level versus 8.5?m), which increases the ongoing difficulty in closing the global sea level budget at the Last Glacial Maximum.