Multiple closely related populations of Poecilia fish have adapted to hydrogen sulfide-rich springs from adjacent nonsulfidic streams, making them an ideal system to study the role of expression variation and structural changes in adaptation. Hydrogen sulfide (H2S) is a potent toxicant that interrupts the mitochondrial respiratory chain and is also associated with severe hypoxia in aquatic environments. Constitutively high levels of dissolved H2S place strong selective pressures on populations. RNA-sequencing of gills from natural and common-garden experiments provide evidence for the genomic and transcriptional basis of adaptation to this extreme environment. Genome-wide gene expression patterns across wild-caught replicated pairs of sulfidic and non-sulfidic populations clustered individuals by habitat type instead of by geographic and phylogenetic similarity. Though most differential gene expression between ecotypes was drainage specific, a small number of genes were consistently differentially expressed in the same direction in all sulfidic and nonsulfidic population pairs. Those shared differentially upregulated genes were associated with enzymatic H2S detoxification and transport of oxidized sulfur species, oxidative phosphorylation, and pathways involved in responses to oxidative stress. In a common garden exposure study we recovered similar patterns of differential expression in wild-caught and laboratory populations that correspond to adaptation to H2S. We found evidence that evolution, and less so ancestral plasticity, is responsible for generating variation in gene expression across replicated pairs of populations. We coupled these findings with a scan for highly differentiated and fixed loci between nonsulfidic and sulfidic populations and found evidence for selection on sulfide detoxification genes in all three drainages. Moreover, the set of loci under positive selection is enriched for differentially expressed loci. Modification of processes associated with H2S detoxification and toxicity through expression-level and sequence-level changes complement each other to mediate elevated H2S tolerance in sulfide spring fishes.