The introduction and establishment of exotic species often result in significant changes in recipient communities and their associated ecosystem services. However, usually the magnitude and direction of the changes are difficult to quantify because there is no pre-introduction data. Specifically, little is known about the effect of marine exotic macrophytes on organic carbon sequestration and storage. Here, we combine dating sediment cores (210Pb) with sediment eDNA fingerprinting to reconstruct the chronology of pre- and post-arrival of the Red Sea seagrass Halophila stipulacea spreading into the Eastern Mediterranean native seagrass meadows. We then compare sediment organic carbon storage and burial rates before and after the arrival of H. stipulacea and between exotic (H. stipulacea) and native (C. nodosa and P. oceanica) meadows since the time of arrival following a Before-After-Control-Impact (BACI) approach. This analysis revealed that H. stipulacea arrived at the areas of study in Limassol (Cyprus) and West Crete (Greece) in the 1930s and 1970s, respectively. Average sediment organic carbon after the arrival of H. stipulacea to the sites increased in the exotic meadows twofold, from 8.4 ± 2.5 g Corg m−2 year−1 to 14.7 ± 3.6 g Corg m−2 year−1, and, since then, burial rates in the exotic seagrass meadows were higher than in native ones of Cymodocea nodosa and Posidonia oceanica. Carbon isotopic data indicated a 50% increase of the seagrass contribution to the total sediment Corg pool since the arrival of H. stipulacea. Our results demonstrate that the invasion of H. stipulacea may play an important role in maintaining the blue carbon sink capacity in the future warmer Mediterranean Sea, by developing new carbon sinks in bare sediments and colonizing areas previously occupied by the colder thermal affinity P. oceanica.