This article explores literary discussions of sovereignty in two medieval Scottish romances, John Barbour's The Bruce (c. 1375) and the anonymous Arthurian romance Golagros and Gawane (c. 1475), both of which respond to the Anglo-Scottish conflicts of the fourteenth and fifteenth centuries and advocate Scottish independence. Premodern European conceptions of sovereignty relied on narratives of recognition to construct and support political claims. This essay argues that these Scottish vernacular texts adapted terms from the larger European discourse to re-imagine the nature of government and freedom through the formal element of a 'sovereign recognition'. While Barbour's The Bruce attempts to distinguish the validity of political claims via the rightful behavior of rulers, ultimately it remains trapped by the prevailing terms of sovereign recognition that require the subjugation of others and the citation of documentary 'proof' to establish authority. By contrast, Golagros and Gawane critiques the use of historical narratives of recognition in determining political relations. This Arthurian romance posits alternative criteria for sovereign recognition that would create a dialogic system of equivalent polities based on personal bonds of mutual acknowledgement. The political thought in both literary texts offers a valuable challenge to current definitions of sovereignty and freedom as located solely within the framework of the territorial nation-state.