Extreme environments test the limits of life; yet, some organisms thrive in harsh conditions. Extremophile lineages inspire questions about how organisms can tolerate physiochemical stressors and whether the repeated colonization of extreme environments is facilitated by predictable and repeatable evolutionary innovations. We identified the mechanistic basis underlying convergent evolution of tolerance to hydrogen sulfide (H2S)-a toxicant that impairs mitochondrial function-across evolutionarily independent lineages of a fish (Poecilia mexicana, Poeciliidae) from H2S-rich springs. Using comparative biochemical and physiological analyses, we found that mitochondrial function is maintained in the presence of H2S in sulfide spring P. mexicana but not ancestral lineages from nonsulfidic habitats due to convergent adaptations in the primary toxicity target and a major detoxification enzyme. Genome-wide local ancestry analyses indicated that convergent evolution of increased H2S tolerance in different populations is likely caused by a combination of selection on standing genetic variation and de novo mutations. On a macroevolutionary scale, H2S tolerance in 10 independent lineages of sulfide spring fishes across multiple genera of Poeciliidae is correlated with the convergent modification and expression changes in genes associated with H2S toxicity and detoxification. Our results demonstrate that the modification of highly conserved physiological pathways associated with essential mitochondrial processes mediates tolerance to physiochemical stress. In addition, the same pathways, genes, and-in some instances-codons are implicated in H2S adaptation in lineages that span 40 million years of evolution.