The massive North Atlantic iceberg discharges of the last glacial period, the so-called Heinrich events (HE), resulted in atmospheric and oceanic responses of the Mediterranean region that remain poorly documented and understood. This paper focuses on the climatic phases termed Heinrich stadials (HS) 4 and 5 generated by the HE 4 and 5 that occurred during a period of similar intermediate global ice volume and greenhouse gas concentrations but with different iceberg discharges and orbital boundary conditions. Our comparison of sea surface temperature and salinity changes with deep water conditions in the Gulf of Lions (planktonic and benthic foraminifera δ18O and δ13C records) and regional pollen-based temperature and precipitation reconstructions in NW Mediterranean for these Heinrich stadials reveal a paradoxical situation. A lower North American iceberg discharge during HS 5 compared to HS 4 is associated with colder and drier conditions in the NW Mediterranean borderlands. During the moderate iceberg discharge of HS 5 a relatively high salinity in the Gulf of Lions lead to stronger Western Mediterranean Deep Water formation and mixing of the surface with the deeper layers. By contrast during HS 4, we suggest that the massive North Atlantic iceberg break-up decreased the salinity of the Gulf of Lions and reduced the wind stress in the Mediterranean, leading to the stratification of the Mediterranean water column and inducing limited upward mixing of cold water, resulting in regional atmospheric warming and wetting compared to HS 5. This work highlights the potential crucial role of local processes in modulating the regional response to a global climate change related with ice-sheet instabilities.