Prejudicial attitudes and discrimination toward gay men is a common social problem in Turkey as it is in many other countries. It is important to understand the reasons behind the prejudice against gay men in a sexist and Muslim country, Turkey. The purpose of the study was to predict attitudes toward gay men with ambivalent attitudes toward men (hostility toward men, and benevolence toward men), questioning religion, and gender differences. Three hundred seventy-two (91 male and 281 female) heterosexual Muslim students from several universities in Ankara completed Attitudes toward Gay men Scale, Ambivalence toward Men Inventory, and Questioning Religion Scale. The mean age of the participants was 22.79 (SD = 3.07). Results, in general, demonstrated that gender differences, benevolence toward men, and questioning religion predicted attitudes toward gay men. Men were more prejudiced against gay men than women. Participants who scored high on benevolence toward men and low on questioning religion were also more prejudiced against gay men than those who scored low on benevolence toward men and high on questioning religion. Further, gender differences was a moderator variable for the association between hostility toward men and attitudes toward gay men. When the regression analyses were performed separately for female and male participants, it was seen that hostility toward men, benevolence toward men, and questioning religion predicted attitudes toward gay men for women whereas for men only benevolence toward men and questioning religion predicted attitudes toward gay men. Results were discussed in the light of relevant literature.