This paper proposes gender differences in responses to recruitment rejections as a previously unexamined mechanism contributing to women’s under-representation in top management. We show that women are less likely than men to consider another job with a prospective employer that has rejected them in the past. We build a theoretical model whereby, because of women’s minority status in senior roles, recruitment rejection triggers uncertainty about their general belonging in the executive domain. Belonging uncertainty, in turn, both leads women to place greater weight than men on fair treatment and negatively affects their perceptions of the fairness of the treatment they receive. This dual process makes women more disinclined than men to apply again to a previously rejecting firm. We test our theory with three studies: A field study using longitudinal archival data from an executive search firm, a survey of executives, and an experiment using executive respondents. The results, which are consistent with our model, have implications for theory and practice regarding gender inequality at the labor market’s upper echelons. In particular, we highlight that women’s supply-side decisions to “lean out” of competition for senior roles must be understood in light of their previous experiences with demand-side employers’ practices.