Significance It has been suggested that, in response to anthropogenic global warming, the Greenland Ice Sheet may reach a tipping point beyond which its current configuration would become unstable. A crucial nonlinear mechanism for the existence of this tipping point is the positive melt-elevation feedback: Melting reduces ice sheet height, exposing the ice sheet surface to warmer temperatures, which further accelerates melting. We reveal early-warning signals for a forthcoming critical transition from ice-core-derived height reconstructions and infer that the western Greenland Ice Sheet has been losing stability in response to rising temperatures. We show that the melt-elevation feedback is likely to be responsible for the observed destabilization. Our results suggest substantially enhanced melting in the near future.