We experimentally investigated whether learning from previous experiences can lead to the establishment of a new mate preference in a wild population of birds. During year one (2001), 63 female collared flycatchers (Ficedula albicollis) bred together with males that we had provided with a novel trait, a red stripe on their white forehead patch (a sexually selected trait). Some color patterns of birds are largely determined by a few genes, and this experiment was designed to mimic the occurrence of mutations in such genes. In the subsequent year (2002), we found that females with previous experience with red-striped males were more likely to pair with red-striped males (76%) than with control males. By contrast, naïve females (i.e., with no previous experience with red-striped males) were not more likely to pair with red-striped males (44%) than with control males. Females paired with red-striped males produced more offspring than females paired with control males, suggesting that males with the novel trait had become favored by selection. Thus, female collared flycatchers appear to quickly learn to associate a novel trait with a suitable mate that, in turn, leads to assortative mating between local mates (i.e., males with the new trait and females with previous experience of the new trait). Our results provide support for the notion that learning may play an important role when the co-evolution of preferences and preferred traits takes different routes in different populations of the same bird species.