Past changes in the density and momentum structure of oceanic circulation are an important aspect of changes in the Atlantic Meridional Overturning Circulation and consequently climate. However, very little is known about past changes in the vertical density structure of the ocean, even very extensively studied systems such as the North Atlantic. Here we exploit the physical controls on the settling depth of the dense Mediterranean water plume derived from the Strait of Gibraltar to obtain the first robust, observations-based, probabilistic reconstruction of the vertical density gradient in the eastern North Atlantic during the last 30,000 years. We find that this gradient was weakened by more than 50%, relative to the present, during the last Glacial Maximum, and that changes in general are associated with reductions in AMOC intensity. However, we find only a small change during Heinrich Event 1 relative to the Last Glacial Maximum, despite strong evidence that overturning was substantially altered. This implies that millennial-scale changes may not be reflected in vertical density structure of the ocean, which may be limited to responses on an ocean-overturning timescale or longer. Regardless, our novel reconstruction of Atlantic density structure can be used as the basis for a dynamical measure for validation of model-based AMOC reconstructions. In addition, our general approach is transferrable to other marginal sea outflow plumes, to provide estimates of oceanic vertical density gradients in other locations.