Despite the centrality of national identity in the exclusionary discourse of the European radical right, scholars have not investigated how popular definitions of nationhood are connected to dispositions toward Muslims. Moreover, survey-based studies tend to conflate anti-Muslim attitudes with general anti-immigrant sentiments. This article contributes to research on nationalism and out-group attitudes by demonstrating that varieties of national self-understanding are predictive of anti-Muslim attitudes, above and beyond dispositions toward immigrants. Using latent class analysis and multilevel models of survey data from 41 European countries, we demonstrate that conceptions of nationhood are heterogeneous within countries and that their relationship with anti-Muslim attitudes is contextually variable. Consistent with expectations, anti-Muslim attitudes are associated with “thicker” conceptions of nationhood in most countries. In Northwestern Europe, however, it is civic nationalism that is linked to greater antipathy toward Muslims. We suggest that in this region, elective criteria of belonging have become fused with exclusionary notions of national culture that portray Muslims as incompatible with European liberal values, effectively legitimating anti-Muslim sentiments in mainstream political culture. This may serve to legitimate anti-Muslim sentiments not only on the radical right, but also among mainstream segments of the Northwestern European public, with important implications for social exclusion and political behavior.