Many studies have shown that better-educated immigrants more frequently report perceived discrimination in the host country than less-educated immigrants. Two different explanations for this discrimination paradox, which is a subcase of the so-called integration paradox, are discussed in the literature. First, with increasing integration, immigrants’ sensitivity to discrimination processes changes. Second, more integrated immigrants are more exposed to discrimination as they have more frequent contact with the majority society, and thus, more actual opportunities for perceived discrimination. We argue that exposure is only effective if immigrants are recognizable as such. Besides other characteristics, first names serve as an indicator of immigrant background. We use respondents’ first name as an exogenous variation in exposure. By analyzing data from the German Socio-Economic Panel (N = 32,043), we show that (i) immigrants with first names considered uncommon in the host country report discrimination disproportionately frequently, (ii) the discrimination paradox is only evident if a name as a marker indicating ethnicity exists, and (iii) there is no such interaction between first name and education, if immigrants are recognizable by phenotypical markers.