Over the last century humans have altered the export of fluvial materials leading to significant changes in morphology, chemistry, and biology of the coastal ocean. Here we present sedimentary, paleoenvironmental and paleogenetic evidence to show that the Black Sea, a nearly enclosed marine basin, was affected by land use long before the changes of the Industrial Era. Although watershed hydroclimate was spatially and temporally variable over the last ~3000 years, surface salinity dropped systematically in the Black Sea. Sediment loads delivered by Danube River, the main tributary of the Black Sea, significantly increased as land use intensified in the last two millennia, which led to a rapid expansion of its delta. Lastly, proliferation of diatoms and dinoflagellates over the last five to six centuries, when intensive deforestation occurred in Eastern Europe, points to an anthropogenic pulse of river-borne nutrients that radically transformed the food web structure in the Black Sea.