This article examines intra-European migration in the early nineteenth century and ways in which the notion of belonging began to change in this mobile age. I will argue that strategies of making someone (not) belong differed on a local and national level and were influenced by intersecting categories of difference. To date, migration history has often focused on structures and policies, or on questions of assimilation and integration, while interactions between migrants and local communities were mostly overlooked. Based on a petition for naturalization, the article looks at one migrant’s attempt to stay in his new region of residence in the early 1840s. Correspondence related to the petition is examined to determine how politics and practices of migration were linked to ideas of belonging and were also an effect of negotiations. Focusing on this case study, I discuss belonging as a means of power, since the sources reflect the constant intersection of social status/class, education, and gender. Thus, inclusion and exclusion were practiced differently before nationality (and race/ethnicity) became established as categories of social inequality.