This article argues that governments play a considerable role in shaping citizens’ attitudes toward Muslim immigrants through the way they regulate religion. European democracies are far from secular, and matters of religious regulation cannot be reduced to abstract values or constitutional clauses. Under conditions of high state support of religion, accommodating new religious minorities involves not only the changing of existing rules but also giving up on long-standing traditions and everyday habits. As a result, citizens see religious newcomers as a threat to their way of life and react with animosity to their practices and demands. We support our argument by combining newly designed survey items with original data on religious regulation in 26 Swiss cantons. Our findings contradict the extant literature and have important implications for the democratic challenges in Europe, the quality of modern immigration societies, and the role of religion in democracy more generally.