In this paper, we investigate how attachment to religion is connected to conservative gender role beliefs and to what extent they, in turn, materialize into fertility decisions. We also test the hypothesis that exposure to gender-progressive political regimes and ideology can weaken this chain of effects, by eroding either the way religion shapes gender roles or the impact of gender beliefs on fertility. Our empirical analysis is based on World Value Survey (WVS) data for five Muslim ex-Soviet Republics vis-à-vis seven other Muslim countries in the neighbouring regions. Results highlight that higher attachment to religion is in both groups associated with more traditional gender roles; however, the link is significantly weaker for the individuals of former communist countries who spent their formative age under Soviet rule. More conservative gender beliefs, in turn, do not translate into higher fertility in Muslim ex-USSR Republics, while the opposite holds for other Muslim countries.