Is opposition to Muslim immigration in Western societies driven by perceptions of a cultural threat? Can shared ideas between natives and immigrants mitigate discrimination against immigrants? We hypothesize that natives’ bias against Muslim immigrants is shaped by the belief that Muslims hold conservative attitudes about women’s rights and that this ideational basis for discrimination is more pronounced among native women. We test this hypothesis in a large-scale field experiment conducted in 25 cities across Germany, during which 3,797 unknowing bystanders were exposed to brief social encounters with confederates who revealed their ideas regarding gender roles. We find significant discrimination against Muslim women, but this discrimination is eliminated when these women signal that they share progressive gender attitudes held by natives. Through an implicit association test and a follow-up survey among German adults, we further confirm the centrality of ideational stereotypes in structuring opposition to immigration. Our findings have important implications for reducing conflict between native-immigrant communities in an era of increased cross-border migration.