Why are naturalization policies in the Gulf so restrictive? And have they always been that way? This research traces how naturalization policies in the UAE have changed over time. Employing primary archival and interview data (collected in the UAE and UK), this paper examines the early stages of the formation of the UAE’s citizenship regime. The research finds that the different stages of the expansion and restriction of citizenship regimes are a reflection of elites’ changing political, economic, and security calculations. The early state modernizers and their British allies played a central role in formalizing the citizenship regime and creating categories of non-citizens, especially from the 1950s onwards. Crucially, state building led to the standardization of identification materials that impacted the Arab and non-Arab populations who were already residing in these territories. Those individuals who could document and trace their patrilineage to tribes present in the UAE since at least 1925 were granted “family books” or “Khulasaat al Gaid,” marking them as ‘full’ citizens. Those who could not trace their lineage to the specific tribes found that their mobility and access to jobs, goods, and services was being increasingly hampered as their status was formalized into the new “non-citizen” categories of ‘guest-workers’ or ‘illegal immigrants’ or ‘bidoon’ (stateless). This paper thus finds that the consolidation of federal power and the standardization and security concerns of the Ministry of Interior (at both the federal and Emirate levels) have not only led to the legal creation of “citizens,” but also constructed and formalized new categories of “non-citizens.” The first contribution of this paper is that it challenges the scholarly and popular treatment of patrilineal and genealogical citizenship regimes as natural outcomes of “Arab culture” and “tribal mentality.” These primordial explanations are challenged by the fact that rulers of competing tribes often encouraged the immigration and integration of (Arab and non-Arab) groups prior to the 1970s. The second contribution of this paper is that it challenges the widely-held assumption that the populations in the territories of Trucial Oman were ethnically homogenous. Rather, it treats the construction of this racial “purity” of citizens as an outcome of the standardization of identities that accompanied nation and state-building projects in the region. The key function of this paper is thus to show how certain populations were privileged and while others were excluded as tribal power was being consolidated and translated into territorial political units.