Persulfide dioxygenases (PDOs), also known as sulfur dioxygenases (SDOs), oxidize glutathione persulfide (GSSH) to sulfite and GSH. PDOs belong to the metallo-β-lactamase superfamily and play critical roles in animals, plants, and microorganisms, including sulfide detoxification. The structures of two PDOs from human and Arabidopsis thaliana have been reported; however, little is known about the substrate binding and catalytic mechanism. The crystal structures of two bacterial PDOs from Pseudomonas putida and Myxococcus xanthus were determined at 1.5- and 2.5-Å resolution, respectively. The structures of both PDOs were homodimers, and their metal centers and β-lactamase folds were superimposable with those of related enzymes, especially the glyoxalases II. The PDOs share similar Fe(II) coordination and a secondary coordination sphere-based hydrogen bond network that is absent in glyoxalases II, in which the corresponding residues are involved instead in coordinating a second metal ion. The crystal structure of the complex between the Pseudomonas PDO and GSH also reveals the similarity of substrate binding between it and glyoxalases II. Further analysis implicates an identical mode of substrate binding by known PDOs. Thus, the data not only reveal the differences in metal binding and coordination between the dioxygenases and the hydrolytic enzymes in the metallo-β-lactamase superfamily, but also provide detailed information on substrate binding by PDOs.