Background: Animal migration requires adaptations in morphological, physiological and behavioural traits. Several of these traits have been shown to possess a strong heritable component in birds, but little is known about their genetic architecture. Here we used 454 sequencing of brain-derived transcriptomes from two differentially migrating subspecies of the willow warbler Phylloscopus trochilus to detect genes potentially underlying traits associated with migration. Results: The transcriptome sequencing resulted in 1.8 million reads following filtering steps. Most of the reads (84%) were successfully mapped to the genome of the zebra finch Taeniopygia gutatta. The mapped reads were situated within at least 12,101 predicted zebra finch genes, with the greatest sequencing depth in exons. Reads that were mapped to intergenic regions were generally located close to predicted genes and possibly located in uncharacterized untranslated regions (UTRs). Out of 85,000 single nucleotide polymorphisms (SNPs) with a minimum sequencing depth of eight reads from each of two subspecies-specific pools, only 55 showed high differentiation, confirming previous studies showing that most of the genetic variation is shared between the subspecies. Validation of a subset of the most highly differentiated SNPs using Sanger sequencing demonstrated that several of them also were differentiated between an independent set of individuals of each subspecies. These SNPs were clustered in two chromosome regions that are likely to be influenced by divergent selection between the subspecies and that could potentially be associated with adaptations to their different migratory strategies. Conclusions: Our study represents the first large-scale sequencing analysis aiming at detecting genes underlying migratory phenotypes in birds and provides new candidates for genes potentially involved in migration.