In this study, we present a novel methodology that may be used to analyze tsunami risk along coastal regions. The application of the proposed methodology is demonstrated for the Eastern Mediterranean coast. Economic, social and environmental dimensions of risk are calculated and aggregated to obtain the overall risk maps for a number of elements at risk (EaR) that are identified from seven countries located along the Eastern Mediterranean coastline. Historical earthquakes that are recorded in the region during the period 1900-2013 are used as data, and probabilistic tsunami modeling is carried out using Monte Carlo analysis. Based on historical data, randomly generated earthquakes are simulated, and wave propagation analysis is performed using NAMI-DANCE software. Inundation depth-damage analysis and exceedance probabilities of tsunami inundations are used to evaluate social and economic risks while the environmental risk is calculated using a binary approach. The overall risk map is constructed in the geographic information system environment. Cairo Agricultural Area in Egypt and Fethiye City in Turkey are identified as high-risk EaR in the Eastern Mediterranean coastline. The new risk assessment methodology may be utilized in coastal regions of the world, and the results obtained for the Eastern Mediterranean may be effectively used in developing preventive measures and disaster management strategies for tsunamis that may develop the region.