This past decade has witnessed a new stream of labor migration arriving in the EU, as a handful of countries in southern and eastern Europe have begun to offer pathways to citizenship for foreign manual laborers. Amongst those who have taken advantage of this offer, Nepali laborers make up a sizable minority, with diasporic communities appearing in the countries offering such pathways, i.e. Portugal, Spain, and Malta. Few of these migrants plan to stay in their arrival country. Instead, most are biding their time until they attain citizenship or permanent residency, after which they plan to move legally to countries in northern Europe—most notably Denmark, Germany, Austria, and Norway—where they believe better economic opportunities await. While such a strategy appears pragmatic, the desire to relocate is far more widespread than circumstances would suggest. Even amongst those living comfortably in southern Europe and those who have already relocated to said northern countries, many are planning to relocate again, often at great risk and personal expense. Such a finding is surprising given that many of these migrants—having spent years as sojourn laborers in other Asian countries—arrive in Europe with the expressed intention of settling permanently. This paper discusses what drives Nepali intra-European labor migration. My hypothesis is that Nepali diasporic communities are caught between two sets of contradictory demands: to settle in the West while remaining “existentially mobile,” and to conform to a European mobility regime that legally allows their presence but remains distrustful of their presence. I examine how labor migrants’ arrival in Europe portends an existential dilemma, wherein they seek to establish themselves within a shifting political and economic landscape, relying on fellow Nepali migrants to help interpret and strategize. I hypothesize that this restlessness is part of an imperfect strategy to rectify the gap between the existential pressures and the material and policy-based difficulties that migrants face.