The relevance of recent migrants’ broader structural position for their destination country identification is studied in this manuscript. In three ways, we build upon previous work referring to an integration paradox, concluding that more structurally integrated migrants turn away from the destination country. First, we extend existing research that mainly tests this for migrants’ educational level, by acknowledging that structural integration also includes migrants’ economic position. Second, we elaborate on the relative deprivation framework by testing how a mismatch between educational and economic position affects destination country identification. Third, we not only study how migrants feel about the native population, used as outcome in most integration paradox studies, but also for a sense of belonging to the destination country. We test our hypotheses cross-sectionally and dynamically using the New Immigrants to the Netherlands Survey. Results indicate that migrants’ educational and economic position hardly affects the way they feel about the native population, whilst a higher structural position does hamper a sense of belonging to the destination country. This latter finding is not explained by a mismatch between educational and economic position, as a mismatch does not systematically affect new immigrants’ feelings about the native population or their sense of belonging.