The decolonizing states of Asia told many stories—about the colonial trauma they endured and the violence that followed in the wake of independence. Seeking to build legitimacy at home, autocrats in the emergent Republics of Korea and China propagated their own stories with fervor. They spoke of sovereign, even civilizational, “recovery”—that is, the salvation of their divided nations from the fatal rise of communism and immoral vestiges of the Japanese empire. By the end of the 20th century, however, these founding narratives were deeply contested and threatened the very political orders that they once justified. How did these narratives become so disputed? And what consequences did such revisionism have on nation-building in the aftermath of colonial, wartime, and authoritarian violence? I address these questions through a comparative historical study of national stories in South Korea and Taiwan. Both democracies came to jettison important, yet different features of their national stories. In South Korea, narratives of “One Korea” remained surprisingly persistent across political parties and sustained longing for unification; meanwhile in Taiwan, narratives of “One China” gradually atrophied into a social—and electoral—taboo. And though South Korean progressives recast pro-Japan narratives as at once collaborationist and authoritarian, Taiwanese progressives opted over time to efface colonial grievances. These alternate narrative patterns offer a unique opportunity to explicate the mutually constitutive processes of political democratization and narrative contestation and illustrate the mechanisms by which new storytellers helped reimagine the nations’ sovereign beginnings and thus, their “democratic” futures. Using primary sources collected over 12 months of archival research in Seoul and Daejeon (South Korea) and Taipei (Taiwan), and in-depth interviews of “storytelling elites”—such as historians, civil society leaders, and journalists—I show that progressive dissenters in South Korea and Taiwan anchored their democratic legitimacy on narratives that helped differentiate them from their autocratic counterparts. Their revisionist efforts, in turn, helped re-found nations after democracy.