The Atlantic-Mediterranean exchange of water at Gibraltar represents a significant heat and freshwater sink for the North Atlantic and is a major control on the heat, salt and freshwater budgets of the Mediterranean Sea. Consequently, an understanding of the response of the exchange system to external changes is vital to a full comprehension of the hydrographic responses in both ocean basins. Here, we use a synthesis of empirical (oxygen isotope, planktonic foraminiferal assemblage) and modeling (analytical and general circulation) approaches to investigate the response of the Gibraltar Exchange system to Atlantic freshening during Heinrich Stadials (HSs). HSs display relatively flat W-E surface hydrographic gradients more comparable to the Late Holocene than the Last Glacial Maximum. This is significant, as it implies a similar state of surface circulation during these periods and a different state during the Last Glacial Maximum. During HS1, the gradient may have collapsed altogether, implying very strong water column stratification and a single thermal and delta O-18(water) condition in surface water extending from southern Portugal to the eastern Alboran Sea. Together, these observations imply that inflow of Atlantic water into the Mediterranean was significantly increased during HS periods compared to background glacial conditions. Modeling efforts confirm that this is a predictable consequence of freshening North Atlantic surface water with iceberg meltwater and indicate that the enhanced exchange condition would last until the cessation of anomalous freshwater supply into to the northern North Atlantic. The close coupling of dynamics at Gibraltar Exchange with the Atlantic freshwater system provides an explanation for observations of increased Mediterranean Outflow activity during HS periods and also during the last deglaciation. This coupling is also significant to global ocean dynamics, as it causes density enhancement of the Atlantic water column via the Gibraltar Exchange to be inversely related to North Atlantic surface salinity. Consequently, Mediterranean enhancement of the Atlantic Meridional Overturning Circulation will be greatest when the overturning itself is at its weakest, a potentially critical negative feedback to Atlantic buoyancy change during times of ice sheet collapse.