Sequestration of plastics in sediments is considered the ultimate sink of marine plastic pollution that would justify unexpectedly low loads found in surface waters. Here, we demonstrate that mangroves, generally supporting high sediment accretion rates, efficiently sequester plastics in their sediments. To this end, we extracted microplastics from dated sediment cores of the Red Sea and Arabian Gulf mangrove (Avicennia marina) forests along the Saudi Arabian coast. We found that microplastics <0.5 mm dominated in mangrove sediments, helping explain their scarcity, in surface waters. We estimate that 50 ± 30 and 110 ± 80 metric tons of plastic may have been buried since the 1930s in mangrove sediments across the Red Sea and the Arabian Gulf, respectively. We observed an exponential increase in the plastic burial rate (8.5 ± 1.2% year−1) since the 1950s in line with the global plastic production increase, confirming mangrove sediments as long-term sinks for plastics.