To investigate past changes in the Mediterranean Overflow Water (MOW) to the Atlantic, we analyzed the strength of the MOW and benthic δ13C along the last 250 kyr at Integrated Ocean Drilling Program (IODP) Site U1389 in the Gulf of Cadiz, near the Strait of Gibraltar. Both the strength of the MOW and the benthic δ13C were mainly driven by precession-controlled fluctuations in the Mediterranean hydrologic budget. Reduced/enhanced Nile discharge and lower/higher Mediterranean annual rainfall at precession maxima/minima resulted in higher/lower MOW strengths at Gibraltar and stronger/weaker Mediterranean overturning circulation. At millennial scale, the higher heat and freshwater loss to the atmosphere during Greenland stadials increased buoyancy loss in the eastern Mediterranean. This enhanced the density gradient with Atlantic water, resulting in a higher MOW velocity in the Gulf of Cadiz. Unlike non-Heinrich stadials, a lower-amplitude increase in velocity was seen during Heinrich stadials (HSs), and a significant drop in velocity was recorded in the middle phase. This weak MOW was especially recognized in Termination I and II during HS1 and HS11. These lower velocities at the depth of Site U1389 were triggered by MOW deepening due to the lower densities of Atlantic intermediate water caused by freshwater released from the Laurentide and Eurasian ice sheets. The intrusion of salt and heat at deeper depths in the Atlantic during HSs and its shoaling at the end could have contributed to drive the changes in the Atlantic Meridional Overturning Circulation during Terminations.