For most species, evolutionary adaptation is not expected to be sufficiently rapid to buffer the effects of human-mediated environmental changes, including environmental pollution. Here we review how key features of populations, the characteristics of environmental pollution, and the genetic architecture underlying adaptive traits, may interact to shape the likelihood of evolutionary rescue from pollution. Large populations of Atlantic killifish (Fundulus heteroclitus) persist in some of the most contaminated estuaries of the United States, and killifish studies have provided some of the first insights into the types of genomic changes that enable rapid evolutionary rescue from complexly degraded environments. We describe how selection by industrial pollutants and other stressors has acted on multiple populations of killifish and posit that extreme nucleotide diversity uniquely positions this species for successful evolutionary adaptation. Mechanistic studies have identified some of the genetic underpinnings of adaptation to a well-studied class of toxic pollutants; however, multiple genetic regions under selection in wild populations seem to reflect more complex responses to diverse native stressors and/or compensatory responses to primary adaptation. The discovery of these pollution-adapted killifish populations suggests that the evolutionary influence of anthropogenic stressors as selective agents occurs widely. Yet adaptation to chemical pollution in terrestrial and aquatic vertebrate wildlife may rarely be a successful "solution to pollution" because potentially adaptive phenotypes may be complex and incur fitness costs, and therefore be unlikely to evolve quickly enough, especially in species with small population sizes.