In the colonial Western Indian Ocean, controlling people’s mobility became a key aspect of state formation. Between the end of the 19th and the first half of the 20th Centuries, efforts to regulate freedom, travel and migration, and labor were central to new definitions and practices of political belonging. These were connected to an emerging realm of subjecthood that was based on an implied recognition of the state as the ultimate political force controlling who could move, when, and where to. In this project, I introduce different histories from colonial India, East Africa and the Persian Gulf and Arabian Peninsula that developed within a broader context of changes brought by abolitionism, the establishment of British protectorates, and the World Wars. I show how these areas became embedded in state-making projects that were intimately tied to the bureaucratization and institutionalization of a system requiring people to own and carry documents to move freely. These ranged from freedom papers and pilgrimage passes to passports and travel permits, as well as a rich set of petitions, applications, endorsements, and appeals. By thinking about these mobile papers, as well as the bureaucratic world that surrounded their production, as instruments of mobility as much as of political identification, I show how definitions and understandings of subjecthood changed during the British colonial period, ultimately setting the basis for post-independence notions of citizenship. My work demonstrates that just as colonial officials crafted new rules for managing colonized populations as mechanisms of legibility, local individuals and political authorities used the bureaucratic realm of mobile papers to adapt, negotiate, assert, and contest their position within an emerging state apparatus. These negotiations remained central for the evolution of political subjecthood and informed future definitions of political belonging in a postcolonial world.