The Alboran Sea is widely recognized to host numerous cold-water coral ecosystems, including the East Melilla Coral Province. Yet, their development through time and response to climatic variability has still to be fully understood. Based on a combined investigation of benthic foraminiferal assemblages, foraminiferal stable isotope compositions, grain size analysis, sediment geochemistry, and macrofaunal quantification, this study identifies key events and processes having governed cold-water coral development at the East Melilla Coral Province between Greenland Stadial 2.1 and the Early Holocene. The transition from Greenland Stadial 2.1 to Greenland Interstadial 1 is associated to a decline of bryozoan communities and their replacement by cold-water corals, together with changes in benthic foraminiferal assemblages and a decrease in the sediment mean grain size. These results suggest that a rapid decrease in bottom currents and the establishment of dysoxic and mesotrophic conditions at the seafloor, possibly associated to enhanced fluvial input, resulted in the decline of bryozoans as the dominant suspension feeding organisms and their replacement by a thriving cold-water coral community. This transition from a bryozoan to a coral dominated environment is concomitant with the beginning of the African Humid Period, confirming that increasing fluvial input could have been a main factor triggering the establishment of cold-water corals in the East Melilla Coral Province during Greenland Interstadial 1. A change in benthic foraminiferal communities and an increase in the sediment mean grain size mark the passage from the Early to Late Greenland Interstadial 1. The current velocity of intermediate water masses is suggested to have increased during the Early to Late Greenland Interstadial 1, whilst simultaneously fluvial input would have reduced. Such changes suggest that the climate became more arid during the second phase of Greenland Interstadial 1.