When we encounter a stranger for the first time, we spontaneously attribute to them a wide variety of character traits based on their facial appearance. There is increasing consensus that learning plays a key role in these first impressions. According to the Trait Inference Mapping (TIM) model, first impressions are the products of mappings between 'face space' and 'trait space' acquired through domain-general associative processes. Drawing on the associative learning literature, TIM predicts that first-learned associations between facial appearance and character will be particularly influential: they will be difficult to unlearn and will be more likely to generalise to novel contexts than appearance-trait associations acquired subsequently. The study of face-trait learning de novo is complicated by the fact that participants, even young children, already have extensive experience with faces before they enter the lab. This renders the study of first-learned associations from faces intractable. Here, we overcome this problem by using Greebles - a class of novel synthetic objects about which participants had no previous knowledge or preconceptions - as a proxy for faces. In four experiments (total N = 640) with adult participants we adapt classic AB-A and AB-C renewal paradigms to study appearance-trait learning. Our results indicate that appearance-trait associations are subject to contextual control, and are resistant to counter-stereotypical experience.