We used extensive data from a long-term study of great tits (Parus major) in the United Kingdom and Netherlands to better understand how genetic signatures of selection translate into variation in fitness and phenotypes. We found that genomic regions under differential selection contained candidate genes for bill morphology and used genetic architecture analyses to confirm that these genes, especially the collagen gene COL4A5, explained variation in bill length. COL4A5 variation was associated with reproductive success, which, combined with spatiotemporal patterns of bill length, suggested ongoing selection for longer bills in the United Kingdom. Last, bill length and COL4A5 variation were associated with usage of feeders, suggesting that longer bills may have evolved in the United Kingdom as a response to supplementary feeding.