The capacity to establish migrants' legal identities is key to states' attempts to control access to their territories. This paper introduces the concept of regimes of proof to shed light on this often-neglected aspect of border and migration control and related migrant struggles. Negotiations around legal identities play a central role in deportation, but also in migrants' access to rights and government services. At the current conjuncture, this tension has become particularly relevant: new digital means of identification such as biometric residency cards or the analysis of mobile phone data are rapidly being introduced across the globe to establish and fix migrants' identities and to determine their country of origin. Drawing on ethnographic research in West Africa and Germany, we consider the implications of shifting regimes of proof in the context of asylum, deportation and regularisation procedures to highlight the centrality of identification to all aspects of migration management.