Measuring the strength of natural selection is tremendously important in evolutionary biology, but remains a challenging task. In this work, we analyse the characteristics of selection for a morphological change (lateral-plate reduction) in the threespine stickleback Gasterosteus aculeatus. Adaptation to freshwater, leading with the reduction or loss of the bony lateral armour, has occurred in parallel on numerous occasions in this species. Completely-plated and low-plated sticklebacks were introduced into a pond, and the phenotypic changes were tracked for 20 years. Fish from the last generation were genotyped for the Ectodysplasin-A (Eda) locus, the major gene involved in armour development. We found a strong fitness advantage for the freshwater-type fish (on average, 20% fitness advantage for the freshwater morph, and 92% for the freshwater genotype). The trend is best explained by assuming that this fitness advantage is maximum at the beginning of the invasion and decreases with time. Such fitness differences provide a quantifiable example of rapid selection-driven phenotypic evolution associated with environmental change in a natural population.