In the current paper we investigate whether gender affects the encoding of leadership behavior. In three studies we found evidence that perceivers had difficulty encoding leadership behaviors into their underlying prototypical leadership traits when the behavior implied an agentic trait and the behavior was enacted by a female. Using a lexical decision making task, in Study 1 we demonstrated that agentic leadership traits were less accessible than communal leadership traits when the leader was female. Additionally, Study 1 also demonstrated that agentic traits were less accessible when the leader was female versus male. In Studies 2a and 2b, we replicated the differences we found for agentic leadership behaviors using perceiver's self-ratings as the dependent variable. Results are discussed both in terms of their implications for future research on gender bias in leadership and their practical implications for eliminating gender bias against females who aspire to leadership positions. (Contains 4 figures.)