Archaeological evidence shows that a predecessor of the 2004 Indian Ocean tsunami devastated nine distinct communities along a 40-km section of the northern coast of Sumatra in about 1394 CE. Our evidence is the spatial and temporal distribution of tens of thousands of medieval ceramic sherds and over 5,000 carved gravestones, collected and recorded during a systematic landscape archaeology survey near the modern city of Banda Aceh. Only the trading settlement of Lamri, perched on a headland above the reach of the tsunami, survived into and through the subsequent 15th century. It is of historical and political interest that by the 16th century, however, Lamri was abandoned, while low-lying coastal sites destroyed by the 1394 tsunami were resettled as the population center of the new economically and politically ascendant Aceh Sultanate. Our evidence implies that the 1394 tsunami was large enough to impact severely many of the areas inundated by the 2004 tsunami and to provoke a significant reconfiguration of the region’s political and economic landscape that shaped the history of the region in subsequent centuries.