This work explores the order of linguistic references to the two genders (e.g., men and women vs. women and men). It argues that a gender is more likely to be mentioned first when it is perceived to have higher relevance in a context rather than lower relevance, and audiences assign stronger relevance to a party when the party is mentioned first rather than second. Studies 1–3 document the current prevalence of male-first conjoined phrases in the public (but not family) domain and link the pattern to historical changes in women’s public presence over the 20th century. Study 4 shows that contextual relevance cues affect the odds of first mention, such that people are more likely to refer to a woman before a man, when the two are in a primary school classroom rather than a corporate office. At the same time, Studies 4 and 5 find that people often choose to reproduce collectively preferred word order patterns (e.g., men and women). Studies 6 and 7 show that these choices matter because people assign more relevance to a party when it comes first rather than second in a conjoined phrase. Overall, this work offers theoretical grounding and empirical evidence for word order as a means of expressing and perpetuating gender stereotypes.