Reactive oxygen species trigger cellular responses by activation of stress-responsive mitogen-activated protein kinase (MAPK) signalling pathways1, 2. Reversal of MAPK activation requires the transcriptional induction of specialized cysteine-based phosphatases that mediate MAPK dephosphorylation3. Paradoxically, oxidative stresses generally inactivate cysteine-based phosphatases by thiol modification and thus could lead to sustained or uncontrolled MAPK activation4, 5. Here we describe how the stress-inducible MAPK phosphatase, Sdp1, presents an unusual solution to this apparent paradox by acquiring enhanced catalytic activity under oxidative conditions. Structural and biochemical evidence reveals that Sdp1 employs an intramolecular disulphide bridge and an invariant histidine side chain to selectively recognize a tyrosine-phosphorylated MAPK substrate. Optimal activity critically requires the disulphide bridge, and thus, to the best of our knowledge, Sdp1 is the first example of a cysteine-dependent phosphatase that couples oxidative stress with substrate recognition. We show that Sdp1, and its paralogue Msg5, have similar properties and belong to a new group of phosphatases unique to yeast and fungal taxa.