Historical tsunamis and tsunami propagation are synthesized in the Eastern Mediterranean Sea region, with particular attention to the Hellenic and the Cyprus arcs and the Levantine basin, to obtain a better picture of the tsunamigenic zones. Historical data of tsunami manifestation in the region are analysed, and compared with current seismic activity and plate interactions. Numerical simulations of potential and historical tsunamis reported in the Cyprus and Hellenic arcs are performed as case studies in the context of the nonlinear shallow-water theory. Tsunami wave heights as well as their distribution function are calculated for the Paphos earthquake of 11 May 1222 and the Crete earthquake of 8 August 1303 as illustrative examples depicting the characteristics of tsunami propagation, and the effects of coastal topography and near-shore amplification. The simulation studies also revealed that the long-normal distributions arc compatible with reported damage. Furthermore, it is necessary to note that high-resolution bathymetry maps are a crucial component in tsunami wave simulations, and this aspect is rather poorly developed in the Eastern Mediterranean. The current study also demonstrates the role of bottom irregularities in determining the wave-height distribution near coastlines. Assuming the probability of occurrence of destructive tsunamigenic earthquakes, these studies will help us to evaluate the tsunami hazard for the coastal plains of the Eastern Mediterranean Sea region. We suggest that future oceanographic and marine geophysical research should aim to improve the resolution of bathymetric maps, particularly for the details of the continental shelf and seamounts.