Major phenotypic changes evolve in parallel in nature by molecular mechanisms that are largely unknown. Here, we use positional cloning methods to identify the major chromosome locus controlling armor plate patterning in wild threespine sticklebacks. Mapping, sequencing, and transgenic studies show that the Ectodysplasin (EDA) signaling pathway plays a key role in evolutionary change in natural populations and that parallel evolution of stickleback low-plated phenotypes at most freshwater locations around the world has occurred by repeated selection of Eda alleles derived from an ancestral low-plated haplotype that first appeared more than two million years ago. Members of this clade of low-plated alleles are present at low frequencies in marine fish, which suggests that standing genetic variation can provide a molecular basis for rapid, parallel evolution of dramatic phenotypic change in nature.