Women’s political leadership has become much more common and often celebrated over the past three decades, while at the same time gendered tropes and sexist treatments of female candidates and office-holders persist. Understanding this contradiction in rising yet oft-criticised female leadership is important for both substantive and normative reasons. While exposure to women’s political leadership has increased, the influence of gendered language – specifically gendered associations in everyday word usage – on public perceptions of women’s fit for political leadership roles has received little scrutiny. I explore how and why this dimension of language shapes gendered perceptions and leadership associations, sometimes in surprising, contradictory, and inconsistent ways. Using cross-national surveys in 10 countries with different gendered linguistic structures, political context, and experience of women’s political leadership, I show deviation from some long-standing assumptions about the gendered associations of certain commonly “desired” leadership traits. These data suggest that public reception to women’s leadership may not be as negative as many electoral outcomes suggest, with positive associations between femininity and key “electability” attributes among the general public. At the same time, there is variation within the population on gendered associations, with younger respondents in countries that speak more gendered languages less likely to hold these positive associations. Taken together, the findings point to potential future gains for women’s leadership aspirations rooted in support from younger generations with less rigid gendered associations with desirable leadership traits. However, those gains are unlikely to accumulate at the same pace across countries where people speak languages that may or may not force them to subconsciously engage the world in a gender dichotomous way.