Understanding the capacity of natural populations to adapt to their local environment is a central topic in evolutionary biology. Phenotypic differences between populations may have a genetic basis, but showing that they reflect different adaptive optima requires the quantification of both gene flow and selection. Good empirical data are rare. Using data on a spatially structured island population of great tits (Parus major), we show here that a persistent difference in mean clutch size between two subpopulations only a few kilometres apart has a major genetic component. We also show that immigrants from outside the island carry genes for large clutches. But gene flow into one subpopulation is low, as a result of a low immigration rate together with strong selection against immigrant genes. This has allowed for adaptation to the island environment and the maintenance of small clutches. In the other area, however, higher gene flow prevents local adaptation and maintains larger clutches. We show that the observed small-scale genetic difference in clutch size is not due to divergent selection on the island, but to different levels of gene flow from outside the island. Our findings illustrate the large effect of immigration on the evolution of local adaptations and on genetic population structure.