Deportation regimes mobilise coercive state powers, but also entail extensive paperwork, the latter of which remains underexplored in deportation studies. Building on ethnographic fieldwork in border police units and a migration-related detention centre in Sweden, this article explores how bureaucratic practices of detecting, detaining and ultimately deporting people whose presence has been illegalised are enforced and legitimated through the use of paperwork. Paperwork, we argue, becomes the ‘signature of the state’ that enables state agencies to assert themselves as ‘rational’ actors, even when their own practices are ridden by dilemmas, inconsistency and sometimes arbitrariness. We show how the same documents that are meant to ensure fairness and accountability in bureaucratic processes may render state actions even more unreadable, and further serve to rationalise and legitimise intrusive, violent and discriminatory state actions. The article thus highlights the importance of considering the often-tedious paperwork as essential to the operation of coercive state powers, such as the detainment and deportation of illegalised persons.