Public opinion research has repeatedly shown that religious people generally report more prejudice against homosexuality. However, previous research exploring the general mechanisms that underpin this relationship mostly relied on Christian samples in North America. Studies outside North America are few in number and limited in the forms of religiosity they address. Of all indicators that have been studied so far, a religious quest orientation was found to be the only one negatively related to anti-gay sentiments. This leaves open the question whether the mechanisms for different forms of religiosity can also be found outside North America. Against that background this research note assesses how religious quest orientation, self-rated religiosity, religious behavior, and authoritarianism are related to prejudice against homosexuality among Christian and Muslim youth aged 14–23 in Flanders (N = 2,834). This study is the first that investigates the relationship between religious quest orientation and anti-gay sentiments among Muslims. For both Christians and Muslims, we found that even taking into account a wide range of social background and religious characteristics, having a religious quest orientation is related to less prejudice toward homosexuality.