This study investigates the multidecadal-scale variability of sea surface temperatures (SSTs) in the convection region of the Gulf of Lion (NW Mediterranean Sea) over the full past 2000 yr (Common Era) using alkenone biomarkers. Our data show colder SSTs by 1.7 °C over most of the first millennium (200–800 AD) and by 1.3 °C during the Little Ice Age (LIA; 1400–1850 AD) than the 20th century mean (17.9 °C). Although on average warmer, those of the Medieval Climate Anomaly (MCA) (1000–1200 AD) were lower by 1 °C. We found a mean SST warming of 2 °C/100 yr over the last century in close agreement with the 0.22 and 0.26 °C/decade values calculated for the western Mediterranean Sea from in situ and satellite data, respectively. Our results also reveal strongly fluctuating SSTs characterized by cold extremes followed by abrupt warming during the LIA. We suggest that the coldest decades of the LIA were likely caused by prevailing negative EA states and associated anticyclone blocking over the North Atlantic resulting in cold continental northeasterly winds to blow over Western Europe and the Mediterranean region.