What was the experience of crossing borders like during the turn of the twentieth century? What channelled and restricted this movement? Importantly, what role did travel papers play in shaping mobility during this stage of globalisation? I explore these questions by looking at a historically hypermobile yet often overlooked region of Central Asia under the Tsarist colonial rule. The latter was among many interested empires around the region: the British conducted excursions from the south while the Qing expanded in the east. While conventional historiography has underscored the Great Game rivalry, my work moves beyond this by focusing on the indigenous inhabitants and their navigation of the changing geopolitical regimes. As these empires drew lines dividing their territories and loyalties through physical demarcations and regulations, many evaded strict rigidities. Cross-border experiences of labourers, merchants, and pilgrims shape my research: their trek across mountains and steppes, on camels or ‘steel horses’ (i.e. railways), led them to engage with socio-legal orders in the shape of documents. From passports and visas to petitions and permit certificates, these aimed to replicate the travellers’ biometric data in the form of physical descriptors. By focusing on the carriers of said papers, I expand beyond the notion of the documentary regime as a mere surveillance tool. Some viewed it as a means of accessing extraterritorial rights and imperial protection. Others found the process of acquisition, including prolonged contact with colonial authorities and expenses, unbearable; among such, one finds stories of counterfeit and subversion, which, in turn, reveals an intricate understanding of the changing mobility regimes.