The accommodation of Muslim minorities in European countries has sparked controversies over the extension of religious rights. Previous research has mostly studied public institutions and debates. But which attitudes toward religious rights do Europeans hold and how can we explain these attitudes? To approach this question, we draw on the novel EURISLAM data set, which allows us for the first time to investigate attitudes of both Muslim minorities and Christian natives in six Western European countries. To explain attitudes, we test the explanatory power of religiosity at the individual level and state-church regimes in both destination and origin countries at the macro level. Overall, Muslims, especially religious Muslims, are more supportive of religious rights than natives. However, we also find that religious natives approve to a greater extent of out-group rights than non-religious natives. We argue that these findings have to be interpreted in light of asymmetric power relationships: Muslim minorities can hardly deny the rights of Christians, as this would undermine their own claims. Similarly, religious natives increasingly constitute a minority in secular societies and may therefore see Muslims as allies in order to strengthen the position of religion in Western Europe. The higher approval of religious individuals challenges the theory on out-group threat, which would lead us to expect that religious individuals are more reluctant to embrace out-group rights. Finally, state-church regimes in the destination countries play a minor role, while the degree of religiosity in the origin countries has an important impact on individual attitudes toward religious rights.