My project represents the first historical examination of Roman identities in the region of modern Tunisia and Algeria after the collapse there of Roman power in the early fifth century. Despite scholarly arguments and assumptions to the contrary, I argue that the idea of being Roman never really ceased to be fundamental among key elements of late-antique and early-medieval society in Africa, even after direct imperial control of the West had long since collapsed. This period saw the emergence of competing political, cultural, and religious definitions of Romanness; but no matter their preferred definition, one critical way that Africans sought to “stay Roman” was by maintaining their ties across the Mediterranean, above all with Italy. This throws into question how we understand the transition from antiquity to the Middle Ages in the Mediterranean in general, and challenges our understanding of when and how the idea of Christendom emerged.