The so-called "gender-equality paradox" is the fact that gender segregation across occupations is more pronounced in more egalitarian and more developed countries. Some scholars have explained this paradox by the existence of deeply rooted or intrinsic gender differences in preferences that materialize more easily in countries where economic constraints are more limited. In line with a strand of research in sociology, we show instead that it can be explained by cross-country differences in essentialist gender norms regarding math aptitudes and appropriate occupational choices. To this aim, we propose a measure of the prevalence and extent of internalization of the stereotype that "math is not for girls" at the country level. This is done using individual-level data on the math attitudes of 300,000 15-year-old female and male students in 64 countries. The stereotype associating math to men is stronger in more egalitarian and developed countries. It is also strongly associated with various measures of female underrepresentation in math intensive fields and can therefore entirely explain the gender-equality paradox. We suggest that economic development and gender equality in rights go hand-in-hand with a reshaping rather than a suppression of gender norms, with the emergence of new and more horizontal forms of social differentiation across genders.