This article analyses the relation between immigrants’ educational attainment and their perceived discrimination. Previous studies in the Netherlands have found that ethnic discrimination is a particularly salient concern among higher educated immigrants, also referred to as the paradox of integration. By using data from the SCIP-project (‘Causes and Consequences of Early Socio-Cultural Integration Processes among New Immigrants in Europe’), I empirically examine, firstly, whether this counterintuitive finding applies to the group of recently arrived Polish and Turkish immigrants in Germany. Secondly, based on three theoretical perspectives, and taking the opportunity structure, immigrants’ awareness, and their relative deprivation into account, I am concerned with the explanation of the integration paradox. Bivariate results confirm the existence of the integration paradox for recent immigrants in Germany. The findings of mediation analysis and effect decomposition indicate that all three theoretical approaches contribute to the explanation; however, the positive relation between educational attainment and perceived discrimination requires slightly different explanations for Poles and Turks. The results further illustrate that it would be misleading to conclude that higher educated immigrants are automatically protected against discriminatory acts.