People tend to have similar beliefs about leaders and men but dissimilar beliefs about leaders and women. A decrease in this perceived incongruity between beliefs about women and leaders might follow from perceived changes in either or both of these stereotypes. In two experiments we investigated the dynamics of this stereotype incongruity by examining cross-temporal perceptions of change in women’s roles and leadership demands. In Experiment 1, participants judged a target group (leaders, men, or women) in a specified year in the past, the present, and the future with regard to gender-stereotypic traits. In Experiment 2, participants evaluated the same target groups in a future society in which the role distribution between the sexes was described as traditional, same-as-today, or equal. Altogether our findings indicate that the perceived incongruity between the leader stereotype and the female stereotype is a dynamic phenomenon. Participants’ beliefs indicated erosion of the perceived incongruity between leaders and women because of a perceived change in women’s roles. We discuss the implications of these beliefs for future social change.