The extent to which adaptation to environmental change occurs via single or multiple advantageous mutations remains an open question, which we examined by studying the spread of melanic forms of the peppered moth in Britain and continental Europe, in response to industrial coal pollution. In Britain, the darkest melanic form is due to the insertion of a transposable element (carb-TE) into a genomic region called ivory. Here, we characterize the spread of melanic forms in continental Europe from historical records and uncover the genetic basis of European melanism using genomic analyses of modern and museum specimens. We show that European melanism is also associated with variants at ivory, but with multiple alleles featuring structural variants, including several transposable elements, though not carb-TE. The primary central European melanic allele is a genetically dominant 805 base pair deletion (sollichau). Interestingly, melanic individuals with either sollichau (deletion) or carb-TE (insertion) alleles show elevated expression of ivory and its effector micro-RNA (mir-193) compared to non-melanic (typica) individuals, suggesting that contrasting structural variants in ivory have similar regulatory effects. A functional role for sollichau was corroborated, serendipitously, by its presence in a typica individual which also contains a linked deletion of mir-193, which is predicted to cancel the melanizing effect of the sollichau deletion. Our results support the idea that there can be many genetic origins of the same adaptive trait within a species, particularly one with a large effective population size and heterogeneous natural habitat, and when many mutations can give rise to the same phenotype.