The facial first impressions literature has focused on trait dimensions, with less research on how social categories (like gender) may influence first impressions of faces. Yet, social psychological studies have shown the importance of categories like gender in the evaluation of behaviour. We investigated whether face gender affects the positive or negative evaluation of faces in terms of first impressions. In Study 1, we manipulated facial gender stereotypicality, and in Study 2, facial trustworthiness or dominance, and examined the valence of resulting spontaneous descriptions of male and female faces. For both male and female participants, counter-stereotypical (masculine or dominant looking), female faces were perceived more negatively than facially stereotypical male or female faces. In Study 3, we examined how facial dominance and trustworthiness affected rated valence across 1,000 male and female ambient face images, and replicated the finding that dominance is more negatively evaluated for female faces. In Study 4, the same effect was found with short stimulus presentations. These findings integrate the facial first impressions literature with evaluative differences based on social categories.