Classical normative theory assumes that to retain their legitimacy democracies should combine relatively closed immigration policies with inclusive citizenship policies. This policy configuration is supposed to provide a viable path to citizenship for those immigrants that can successfully pass through the selective immigration gate and settle in a receiving country. This argument relies on a hitherto untested empirical claim, namely that greater restrictiveness in immigration increases the propensity of immigrants to naturalize. This claim also contradicts assumptions of cosmopolitan theorists who deny that this negative relationship exists. In this paper, we provide estimates of the effect of the openness of immigration regimes on naturalization propensity. To do so, we identify first-generation immigrants and use the information about the timing of immigration in 6 rounds of the European Social Survey (ESS) across 17 Western European destination countries. Study 1 zooms in on the Eastern European enlargement to analyze the effect of quasi-random variation in the timing of the lifting of residual restrictions for migrants from the new EU member states and their levels of naturalization. Study 2 zooms out to analyze the general effect of differences in immigration restrictions that non-free movers were exposed to compared to free movers. Both studies support the implicit empirical claim in the classical normative literature. Immigrants arriving as (new) free movers naturalize less than other immigrants. However, for non-free movers alone, the degree of immigration restrictions does not matter according to most models. Hence, our analyses highlight the naturalization-undermining effect of open borders specifically and thus complicate normative prescriptions that vouch for both open borders and inclusive citizenship. Still, considering that the payoff of naturalization is significantly reduced if one already shares citizenship in a supranational union that comes with many other rights, these results may not apply outside supranational unions and thus beyond Europe.