This paper adopts interwar Libya as a lens to explore the dynamic relationship between frontiers and citizenship in the history of twentieth-century European colonial expansion. Upon its conquest of the Ottoman Libyan provinces in 1911-12, Italy—like all colonial states—immediately sought to define the scope of its territorial sovereignty by delineating and fortifying the borders of its new so-called “fourth shore” in North Africa. At the same time, beginning in 1911, the Italian government initiated a piecemeal sequence of legislation that, over nearly three decades, would continually redefine the bounds of Italian citizenship vis-à-vis its overseas possessions. The question of who belonged within the domain of Italianness (Italianità) became a particular state fixation, considering the ten million Africans over whom Rome claimed sovereignty by 1939. The project of defining Italian citizenship in colonial Libya was complicated by the mobility of large swaths of the local population. During the Italian colonial period, tens if not hundreds of thousands of Libyans fled Italian rule and took refuge across the frontiers in neighboring countries such as Tunisia and Egypt. Based on deep archival research in two key Italian state archives, this paper explores the range of the Italian colonial state’s responses to the challenges of Libyan cross-border mobility, and the impact that this little-known aspect of colonial governance had on the articulation of its empire-wide citizenship regime. How did the Italian government view and keep track of its mobile Libyan subjects, and how did it seek to define and legislate different criteria and norms for membership for them in its more expansive Italian political community? And how might mobility as a defining feature of the Libyan experience of Italian colonialism complicate historical understandings of modern Italy as an imperial state more broadly, while also helping us grapple with the legacy of the Italian period in shaping notions of national citizenship and belonging across North Africa today? To answer these questions, the paper begins by highlighting a number of disputes between the Italian and Egyptian governments over the juridical status of Libyan refugees living in various Egyptian cities and towns—an ongoing occurrence throughout the interwar period. It then demonstrates the impact of Libyan cross-border mobility by illuminating the debate that erupted among Italian colonial officials in the late-30s over a new legal category known as “Special Italian Citizenship,” which was to be reserved for loyal Muslim Libyans.