It has been proposed that ~3.4 billion years ago an ocean fed by enormous catastrophic floods covered most of the Martian northern lowlands. However, a persistent problem with this hypothesis is the lack of definitive paleoshoreline features. Here, based on geomorphic and thermal image mapping in the circum-Chryse and northwestern Arabia Terra regions of the northern plains, in combination with numerical analyses, we show evidence for two enormous tsunami events possibly triggered by bolide impacts, resulting in craters ~30 km in diameter and occurring perhaps a few million years apart. The tsunamis produced widespread littoral landforms, including run-up water-ice-rich and bouldery lobes, which extended tens to hundreds of kilometers over gently sloping plains and boundary cratered highlands, as well as backwash channels where wave retreat occurred on highland-boundary surfaces. The ice-rich lobes formed in association with the younger tsunami, showing that their emplacement took place following a transition into a colder global climatic regime that occurred after the older tsunami event. We conclude that, on early Mars, tsunamis played a major role in generating and resurfacing coastal terrains.