Besserer Rayas et al. Comparative Migration Studies (2024) 12:47 became beneficiaries of Colombia’s push to close paperwork gaps in its citizenship and immigration regimes. Especially in contexts of international displacement (i.e., forced migration), origin countries may not be capable or willing to issue, apostille, or notarize documents such as birth certificates, passports, or criminal records; people on the move may be unable to obtain these documents. This situation leads to significant administrative barriers in residence countries that manage displaced populations through immigration rather than asylum law and policy, an increasingly common practice worldwide (Selee et al., 2024). While asylum systems are designed to pardon lacking documentation regarding both personal identification and burden of proof of persecution (Art. 93 UNHCR 2019), this is not the case for immigration regimes; it thus increases the risk of prolonged irregularity and statelessness. Against this background, we define paperwork gaps as the mismatch between the documents a residence country requires and the documents people on the move – particularly in contexts of international displacement – can feasibly provide. How can states close such paperwork gaps? In this article we discuss four modifications that reduced paperwork gaps in Colombia in the context of the rapid increase of Venezuelan displacement. While various studies shed light on Colombia’s innovative, yet not faultless, regularization policies (e.g., Bahar et al., 2018; Del Real, 2022; Selee & Bolter, 2022), the efforts to reduce bureaucratic hurdles for family reunification and naturalization have received less attention. Nor have the institutional processes that facilitated bridging paperwork gaps been analyzed in detail. In this article, we thus examine four implemented measures: (a) the reunification permit for Colombians and their families expelled from Venezuela; (b) the modified procedures to acquire Colombian nationality through birth, as to reduce statelessness among Venezuelans’ children born in Colombia; (c) the changed naturalization processes for adults born in Venezuela but who can claim Colombian nationality; and (d) the changed requirements of documentary evidence to access the main regularization mechanism, the Temporary Protection Permit (PPT, following the Spanish acronym), implemented in 2020. Through analyzing the paper bridges Colombia built to close paperwork gaps in these four policy domains, we show how residence countries can adapt and innovate within their citizenship and immigration regimes to react to large-scale international displacement. Our analysis lies at the state level; we focus on policy on paper by reviewing relevant documents and decrees as well as by interviewing policymakers. Based on repeated fieldwork trips to Colombia (as part of a larger project), we also include individual-level information from 30 interviews with recently arrived displaced people, lawyers, and NGO leaders. While we do not provide an overall normative assessment of Colombia’s policy response to Venezuelan displacement, we recognize that it has in part shied away from its legal obligation of recognizing Venezuelans as refugees under the Cartagena refugee definition (Freier et al., 2022; Freier & Gómez García, 2022). It has also hid legal fragility and even produced illegality, perhaps surprisingly given its straightforward immigration application procedures, pro-immigrant political discourse, and weak immigration enforcement (Del Real, 2022). These factors have left hundreds of thousands of Venezuelans unable to access rights in practice, thus many challenges remain for Colombia to reach full coverage and offer rights in the long term to all Venezuelans. Colombia nevertheless offers important lessons on bridging paperwork gaps for other receiving Page 2 of 20