Past and present environmental conditions over the Holocene along the Algerian coast involve complex atmosphere-hydrosphere-biosphere interactions and anthropogenic activities on adjacent watersheds. Atlantic Ocean surface waters entering the western Mediterranean Sea at the Gibraltar Strait create the Algerian Current, which flows along the North African coast in a succession of strong and large-scale eddies. Deep-water upwelling plumes are other recurrent hydrological features of the Algerian margin affecting regional environmental features. However, vegetation and paleohydrological changes that have occurred over the Holocene have not yet been described. To bridge this gap, a suite of paleoclimate proxies was analysed in marine core MD04-2801 (2067 m water depth) at a secular-scale resolution over the last 14 kyrs BP. Terrestrial (pollen grains) and marine (dinoflagellate cysts or dinocysts) palynological assemblages, as well as sedimentological (grain-size analysis and XRD-based quantitative analysis of clay minerals) and biomarkers (alkenones and n-alkanes), were determined to explore the links between past sea surface hydrological conditions and regional environmental changes on nearby watersheds.The over-representation of heterotrophic dinocyst taxa (Brigantedinium spp.) indicates strong planktonic productivity in the study area. Results shows that the links between dryness on land and surface hydrological conditions are expressed by: (i) recurrent upwelling cells during the relatively dry climate conditions of the Younger Dryas (12.7 to 11.7 ka BP), the Early Holocene (11.7 to 8.2 ka BP) and from 6 ka BP onwards, (ii) enhanced fluvial discharges between 8.2 and 6 ka BP during the African Humid Period concomitant with the colonization of coastal lands by Mediterranean forest. Middle to Late Holocene transition around 4.2 ka BP characterizes by the intense event reffered to here as the Algerian Mega Drought (4.3 to 3.9 ka BP).