Encounters with strangers bear potential for social conflict and stress, but also allow the formation of alliances. First impressions of other people play a critical role in the formation of alliances, since they provide a learned base to infer the other's future social attitude. Stress can facilitate emotional memories but it is unknown whether stress strengthens our memory for newly acquired impressions of other people's personality traits. To answer this question, we subjected 60 students (37 females, 23 males) to an impression-formation task, viewing portraits together with brief positive vs. negative behavior descriptions, followed by a 3-min cold pressor stress test or a non-stressful control procedure. The next day, novel and old portraits were paired with single trait adjectives, the old portraits with a trait adjective matching the previous day's behavior description. After a filler task, portraits were presented again and subjects were asked to recall the trait adjective. Cued recall was higher for old (previously implied) than the novel portraits' trait adjectives, indicating validity of the applied test procedures. Overall, recall rate of implied trait adjectives did not differ between the stress and the control group. However, while the control group showed a better memory performance for others' implied negative personality traits, the stress group showed enhanced recall for others' implied positive personality traits. This result indicates that post-learning stress affects consolidation of first impressions in a valence-specific manner. We propose that the stress-induced strengthening of memory of others' positive traits forms an important cue for the formation of alliances in stressful conditions.