It is well established that differences in migratory behavior between populations of songbirds have a genetic basis but the actual genes underlying these traits remains largely unknown. In an attempt to identify such candidate genes we de novo assembled the genome of the willow warbler Phylloscopus trochilus, and used whole-genome resequencing and a SNP array to associate genomic variation with migratory phenotypes across two migratory divides around the Baltic Sea that separate SW migrating P. t. trochilus wintering in western Africa and SSE migrating P. t. acredula wintering in eastern and southern Africa. We found that the genomes of the two migratory phenotypes lack clear differences except for three highly differentiated regions located on chromosomes 1, 3, and 5 (containing 146, 135, and 53 genes, respectively). Within each migratory phenotype we found virtually no differences in allele frequencies for thousands of SNPs, even when comparing geographically distant populations breeding in Scandinavia and Far East Russia (>6000 km). In each of the three differentiated regions, multidimensional scaling-based clustering of SNP genotypes from more than 1100 individuals demonstrates the presence of distinct haplotype clusters that are associated with each migratory phenotype. In turn, this suggests that recombination is absent or rare between haplotypes, which could be explained by inversion polymorphisms. Whereas SNP alleles on chromosome 3 correlate with breeding altitude and latitude, the allele distribution within the regions on chromosomes 1 and 5 perfectly matches the geographical distribution of the migratory phenotypes. The most differentiated 10 kb windows and missense mutations within these differentiated regions are associated with genes involved in fatty acid synthesis, possibly representing physiological adaptations to the different migratory strategies. The ∼200 genes in these regions, of which several lack described function, will direct future experimental and comparative studies in the search for genes that underlie important migratory traits.