This dissertation explores what it meant that the federal government could not deport people it identified as undesirable, even as it enacted increasingly strict immigration protocols in the first decades of the twentieth century. The "undeportables" serve as an entry point to investigate how the processes of immigration and deportation created contradictions between sovereignty and rights and how bureaucrats in the United States and their international counterparts resolved those contradictions. Their attempts to reconcile this problem determined who had access to the nation-state and reimagined an increasingly interconnected world where every person had rights. The story of undeportable migrants illustrates how American foreign policy reshaped other governmental initiatives, such as the development of an immigration and deportation apparatus to manage foreign bodies in the United States. The US nonrecognition of Russia through the 1920s offers a vibrant site to explore American conceptions of citizenship, governmental responsibility, and international rights. Russian immigrants were the most visible de facto stateless migrants that encountered the American government in the first decades of the twentieth century, but they were far from the only ones. During this period, the rapidly shifting borders in Eurasia rendered many other foreign-born persons in the United States unable to access diplomatic protection from their country of origin. Set against the backdrop of the United States emergence as an imperial power from the turn of the century through World War II, the dissertation reconstructs the transnational networks, nation-state power dynamics, and emerging rights practices that marked a shift in rights talk. Attention to this shift reveals the mutual imbrication of transnational networks and nation-state sovereignty and repositions the United States as a participant within the rights discourse, not a bystander to it. Understanding undeportable migrants as part of the new history of human rights reframe the history of migration as constitutive of diplomatic history. By examining the processes of migration and deportation through career officials, instead of policymakers and migrants themselves, I situate immigration management as the front line of the federal government's foreign diplomacy. The realm of migration, encompassing movement within and across national borders, is the first site where diplomatic decisions play out and thus offers a litmus test for the viability of American foreign decisions. The people responsible for reconciling undeportables were not policymakers, individual migrants, or activists, but most often mid-level bureaucrats attempting to make sense of conflicting policies and visions of world order. That such individuals maintained the cogs of the international machine is even more notable because of how often their work remains invisible. More often than not, their success was in rendering their labor imperceptible. The dissertation uncovers their struggles and negotiations and establishes the significance of their labor in constructing and maintaining the international order. In focusing on the influence of rogue bureaucrats and opportunistic businesses in this experimental period, this dissertation explains the active role of the informal transnational realm in the making of US foreign policy and the formalization of international human rights.