Research into the relationship between religion and anti-gay attitudes frequently focuses on Christianity. We explored the role of religiosity dimensions, previous contact, and factors in the dual-process motivation model as predictors of explicit and implicit anti-gay attitudes in samples of Muslims and Atheists. The explicit and implicit attitudes of Muslims were more negative than the attitudes of Atheists. Explicit attitudes were more negative towards gay men than lesbians; implicit attitudes were negative towards gay men but were unexpectedly positive towards lesbians. In regression analyses, religious fundamentalism and extrinsic religious orientations (Study 1), and contact and right-wing authoritarianism (Study 2) were strong significant predictors of explicit anti-gay attitudes. Interestingly, none of the factors of interest predicted implicit anti-gay attitudes. These findings reveal a strong link between Islam and explicit anti-gay attitudes, but suggest that the relationship between religion and implicit anti-gay attitudes may be more complex than previously thought.