Mega-tsunami have affected much of the coastline of Australia over the past millennium. Such catastrophic waves have left an imprint consisting predominently of bedrock sculpturing of the rocky coastline and deposition of marine sediments to elevations reaching 130 mabove sea level. One of the largest of these events occurred in eastern Australia in the fifteenth century. This event may be related to the Mahuika impact crater found at 48.38 S, 166.48 E on the continental shelf 250 km south of New Zealand. A comet at least 500 m in diameter formed the crater. Maori and Aboriginal legends allude to significant cosmogenic events in the region, while Aboriginal legends about tsunami are common along the eastern Australian coast. Evidence for legends that could describe the impact of a cosmogenic tsunami also exists in NW Australia. Here geological evidence of a single megatsunami as recent as in the seventeenth century covers 1500 km of coastline. We term this event Wandjina after the artwork related to the legends. More attention should be given to oral traditions in searching globally for other sites of significant mega-tsunami.