The starkly different histories and institutions in the eastern and western member states of the European Union (EU) suggest different roles of being non-native in these two regions. In this paper we study the roles of foreign origin and citizenship in the comparative East-West perspective. Our results indicate that while it is immigrant status that is of key importance in the western EU member states, both immigrant status and citizenship matter in the eastern EU member states, their roles depending on gender. We find some evidence that it is the Russian ethnic minority in Estonia and Latvia that drives the relationships between being non-citizen and labor market outcomes that we find in the eastern EU member states.