This essay places Marie de France’s lai “Yonec” (ca. 1150–1200) and the anonymous Middle English romance King Horn (ca. 1250–1300) in conversation with critical Indigenous theories of relational, land-based sovereignty and resurgence. At first, “Yonec” and King Horn appear to reinscribe a Western form of sovereignty based on exclusive territorial control. Both works offer alternative models of sovereignty and self-determination, however, in their depictions of cooperative, lithic alliance between stone and female consorts. Adopting the term lithic sovereignty to describe the works’ relation-based sovereign imaginaries, this essay first follows the King Horn narrator’s depiction of Godhild’s hermetic retreat into stone when Saracens conquer her husband’s realm. Then it turns to the nameless lady of “Yonec” and her implausible escape from her jealous husband’s tower, facilitated by the very stone that had seemed to entrap her. Drawing on critical Indigenous studies, legal studies, and ecomaterialism, this essay concludes that both King Horn and “Yonec” offer a medieval British imaginary of lithic relational sovereignty that runs counter to teleological, naturalizing narratives of Euro-Western origins.