We report the first experience of deriving the magnitudes of prehistoric earthquakes in southeastern Gorny Altai from the size of largest landslides they triggered using an empirical correlation between the earthquake magnitude and the volume of associated landslides. The applicability of this relationship to the Altai region has been checked against data on the M= 7.5 Chuya earthquake of 2003 that induced a great landslide event. The paleoearthquake magnitudes derived from landslide volume are the minimum estimates; the largest magnitudes of earthquakes of about the same size and location as the Chuya event have been predicted with a simplified linear dependence of earthquake magnitude versus detachment length. The magnitudes obtained with the new approach are of a satisfactory accuracy improving proportionally for younger earthquakes. The estimates spanning magnitudes from 6.9 to largest possible in nature indicate high seismic activity of the area through the Holocene and its seismotectonic identity with the Mongolian Altai.