Tsunami events in antiquity had a profound influence on coastal societies. Six thousand years of historical records and geological data show that tsunamis are a common phenomenon affecting the eastern Mediterranean coastline. However, the possible impact of older tsunamis on prehistoric societies has not been investigated. Here we report, based on optically stimulated luminescence chronology, the earliest documented Holocene tsunami event, between 9.91 to 9.29 ka (kilo-annum), from the eastern Mediterranean at Dor, Israel. Tsunami debris from the early Neolithic is composed of marine sand embedded within fresh-brackish wetland deposits. Global and local sea-level curves for the period, 9.91-9.29 ka, as well as surface elevation reconstructions, show that the tsunami had a run-up of at least ~16 m and traveled between 3.5 to 1.5 km inland from the palaeo-coastline. Submerged slump scars on the continental slope, 16 km west of Dor, point to the nearby "Dor-complex" as a likely cause. The near absence of Pre-Pottery Neolithic A-B archaeological sites (11.70-9.80 cal. ka) suggest these sites were removed by the tsunami, whereas younger, late Pre-Pottery Neolithic B-C (9.25-8.35 cal. ka) and later Pottery-Neolithic sites (8.25-7.80 cal. ka) indicate resettlement following the event. The large run-up of this event highlights the disruptive impact of tsunamis on past societies along the Levantine coast.