Pseudomonas aeruginosa, an opportunistic pathogen of humans, uses quorum sensing (QS) to regulate the production of extracellular products that can benefit all members of the population. P. aeruginosa can police QS-deficient cheaters by producing hydrogen cyanide, which is also QS regulated; however, the mechanism by which cooperators selectively protect themselves from the toxicity of cyanide remained unresolved. Here, we show that a cyanide-insensitive terminal oxidase encoded by cioAB provides resistance to cyanide, but only in QS-proficient strains. QS-deficient cheaters do not activate cioAB transcription. QS-mediated regulation of cioAB expression depends on production of both cyanide by cooperators (which is QS regulated) and reactive oxygen species (ROS) from cheaters (which is not QS regulated). This type of regulatory system allows cooperating populations to respond, via ROS, to the presence of cheaters, and might allow them to defer the substantial metabolic cost of policing until cheaters are present in the population.