The role of natural selection in shaping adaptive trait differentiation in natural populations has long been recognized. Determining its molecular basis, however, remains a challenge. Here, we search for signals of selection in candidate genes for colour and its perception in a passerine bird. Pied flycatcher plumage varies geographically in both its structural and pigment-based properties. Both characteristics appear to be shaped by selection. A single-locus outlier test revealed two of fourteen loci to exhibit significantly elevated signals of divergence. The first of these, the follistatin gene, is expressed in the developing feather bud and found in pathways with genes that determine the structure of feathers and may thus be important in generating variation in structural colouration. The second is a gene potentially underlying the ability to detect this variation: SWS1 opsin. These two loci were most differentiated in two Spanish pied flycatcher populations, which are also among the populations that have the highest ultraviolet reflectance. The follistatin and SWS1 opsin genes, thus provide strong candidates for future investigations on the molecular basis of adaptively significant traits and their co-evolution.