Paleoseismological surveys combined with computer simulation of tsunamis disclosed for the first time that multi-segment inter-plate earthquakes along the Kuril trench off Hokkaido had generated greater tsunami than previously reported. Great earthquakes with magnitudes ~8 ruptured single segments (on rupture segments 100-200km long) over the past two centuries. We use deposits of prehistoric tsunamis, extending kilometers inland, and dated volcanic ash to show that unusually large tsunamis occurred about every 500 years on average over the past 2,000-7,000 years, most recently ~350 years ago. Numerical simulations of these tsunamis are best explained by earthquakes that rupture multiple segments (~300km) along the southern Kuril trench.