Although the Gulf of Aqaba-Eilat is located in the tectonically active northern Red Sea, it has been described as low-risk with regard to tsunami activity because there are no modern records of damaging tsunami events and only one tsunami (1068 AD) referred to in historical records. However, this assessment may be poorly informed given that the area was formed by and is located along the seismically active Dead Sea Fault, its population is known to fluctuate in size and literacy in part due to its harsh hyper-arid climate, and there is a dearth of field studies addressing the presence or absence of tsunamigenic deposits. Here we show evidence from two offshore cores for a major paleotsunami that occurred ~2300 years ago with a sedimentological footprint that far exceeds the scarce markers of the historically mentioned 1068 AD event. The interpretation is based on the presence of a laterally continuous and synchronous, anomalous sedimentological deposit that includes allochtonous inclusions and unique structural characteristics. Based on sedimentological parameters, these deposits could not be accounted for by other transport events, or other known background sedimentological processes.