The last deglaciation is one of the best constrained global-scale climate changes documented by climate archives. Nevertheless, understanding of the underlying dynamics is still limited, especially with respect to abrupt climate shifts and associated changes in the Atlantic Meridional Overturning Circulation (AMOC) during glacial and deglacial periods. A fundamental issue is how to obtain an appropriate climate state at the Last Glacial Maximum (LGM, 21,000 years before present, 21ka BP) that can be used as an initial condition for deglaciation. With the aid of a comprehensive climate model, we found that initial ocean states play an important role on the equilibrium time scale of the simulated glacial ocean. Independent of the initialization the climatological surface characteristics are similar and quasi-stationary, even when trends in the deep ocean are still significant, which provides an explanation for the large spread of simulated LGM ocean states among the Paleoclimate Modeling Intercomparison Project phase 2 (PMIP2) models. The simulated ocean state with most realistic AMOC is characterized by a pronounced vertical stratification, in line with reconstructions. Freshwater perturbation experiments further suggest that response of the glacial ocean is distinctly dependent on the ocean background state, i.e. only the state with robust stratification shows an overshoot behavior in the North Atlantic. We propose that the salinity stratification represents a key control on the AMOC pattern and its transient response to perturbations. Furthermore, additional experiments suggest that the stratified deep ocean formed prior to the LGM during a time of minimum obliquity (~27ka BP). This indicates that changes in the glacial deep ocean already occur before the last deglaciation. In combination, these findings represent a new paradigm for the LGM and the last deglaciation, which challenges the conventional evaluation of glacial and deglacial AMOC changes based on an ocean state derived from 21ka BP boundary conditions. During glacial periods of the Late Pleistocene, an abundance of proxy data demonstrates the existence of large and repeated, millennial-scale climate changes, known as Dansgaard-Oeschger (DO) events. This ubiquitous feature of rapid glacial climate change can be extended back as far as 800 ka BP in the ice core record, and has drawn broad attention within the science and policy making communities alike. Many studies have been dedicated to investigating the underlying causes of these changes, however a coherent mechanism remains elusive. Using a fully-coupled climate model, we show that the non-linear responses of the glacial ocean to Northern Hemisphere Ice Sheets (NHIS) volume changes in the coupled atmosphere-ocean system can explain the occurrence of rapid glacial climate shifts. The global climate responses, including abrupt warming in the North Atlantic and a shift of the tropical rain belts, are generally consistent with empirical evidence. A hysteresis analysis with respect to changes of the NHIS suggests that two distinct glacial climate modes coexist at identical intermediate ice sheet volumes. Notably, minor shifts in the NHIS and atmospheric carbon dioxide can trigger the rapid climate transitions, which occur due to a local positive atmosphere-ocean-sea ice feedback in the North Atlantic at intermediate ice-sheet volume. Our results demonstrate that this distinct glacial climate sensitivity to forcing changes is associated with tempo-spatial variations in the internal variability of sea-ice cover and surface air temperature in the northern North Atlantic and Nordic Sea. In conclusion, the hysteresis of the glacial ocean with respect to ice-sheet variation provides the first coherent concept for understanding the recorded millennial-scale variability and abrupt climate changes in the coupled atmosphere-ocean system, as well as their linkages to intermediate ice-sheet volume during glacials.