Observations from repeat-pass airborne laser altimetry, acquired in 1996 and 2002, indicate an anomalous positive ice-surface elevation change for the central accumulation area of the largest ice cap in the Eurasian Arctic; Austfonna, eastern Svalbard. The increase is equivalent to 35% of the long-term annual accumulation rate and coincides with the loss of perennial sea ice in the adjacent Barents Sea, which we conclude is the most likely explanation for the increase. Extrapolation of the observed trends in sea ice decline, over the next 50 years, suggests large perturbations in the mass-balance of other Arctic ice masses may be expected.