The greatness of Majapahit in the past is preserved through archaeological, written records, and oral story within local communities. This article examines the oral stories of the Majapahit legacy on the Pantar, Sabu, and Sumbawa Islands. Data were collected through in-depth interviews and observations. Each island’s community presents different versions and perspectives on Majapahit. In Pantar, the Munaseli people portray Majapahit as a colonizer and destroyer of the Munaseli kingdom, while their neighbours, the Pandai, view Majapahit as an ally who helped them defeat Munaseli. On Sumbawa, Gajah Mada is considered an ancestor from U’hu, and on Sabu Island, Majapahit appears as a figure named Maja, who left a legacy of powerful memory. The analysis reveals seven distinct versions of these oral narratives by employing memory, oral history, and topoi approaches. Common topoi emerge as key patterns, such as arrival, warfare, name adaptation, and the construction of local historiographies connected to Majapahit. These oral narratives serve as essential components to reaffirm a proto-nationality once spread by Majapahit and, simultaneously, as a ‘tool’ to legitimize oral historical accounts in these regions.