Transition of an evolving population to a new adaptive optimum is predicted to leave a signature in the distribution of effect sizes of fixed mutations. If they affect many traits (are pleiotropic), large effect mutations should contribute more when a population evolves to a farther adaptive peak than to a nearer peak. We tested this prediction in wild threespine stickleback fish (Gasterosteus aculeatus) by comparing the estimated frequency of large effect genetic changes underlying evolution as the same ancestor adapted to two lake types since the end of the ice age. A higher frequency of large effect genetic changes (quantitative trait loci) contributed to adaptive evolution in populations that adapted to lakes representing a more distant optimum than to lakes in which the optimum phenotype was nearer to the ancestral state. Our results also indicate that pleiotropy, not just optimum overshoot, contributes to this difference. These results suggest that a series of adaptive improvements to a new environment leaves a detectable mark in the genome of wild populations. Although not all assumptions of the theory are likely met in natural systems, the prediction may be robust enough to the complexities of natural environments to be useful when forecasting adaptive responses to large environmental changes.