Evolutionary theory predicts an interactive process whereby spatiotemporal environmental heterogeneity will maintain genetic variation, while genetic and phenotypic diversity will buffer populations against stress and allow for fast adaptive evolution in rapidly changing environments. Here, we study color polymorphism patterns in pygmy grasshoppers (Tetrix subulata) and show that the frequency of the melanistic (black) color variant was higher in areas that had been ravaged by fires the previous year than in nonburned habitats, that, in burned areas, the frequency of melanistic grasshoppers dropped from ca. 50% one year after a fire to 30% after four years, and that the variation in frequencies of melanistic individuals among and within populations was genetically based on and represented evolutionary modifications. Dark coloration may confer a selective benefit mediated by enhanced camouflage in recently fire-ravaged areas characterized by blackened visual backgrounds before vegetation has recovered. These findings provide rare evidence for unusually large, extremely rapid adaptive contemporary evolution in replicated natural populations in response to divergent and fluctuating selection associated with spatiotemporal environmental changes.