There have been very few reports on protein domains that specifically recognize sulfur. Here we present the crystal structure of the sulfur-binding domain (SBD) from the DNA phosphorothioation (PT)-dependent restriction endonuclease ScoMcrA. SBD contains a hydrophobic surface cavity that is formed by the aromatic ring of Y164, the pyrolidine ring of P165, and the non-polar side chains of four other residues that serve as lid, base, and wall of the cavity. The SBD and PT-DNA undergo conformational changes upon binding. The S187RGRR191 loop inserts into the DNA major groove to make contacts with the bases of the GPSGCC core sequence. Mutating key residues of SBD impairs PT-DNA association. More than 1000 sequenced microbial species from fourteen phyla contain SBD homologs. We show that three of these homologs bind PT-DNA in vitro and restrict PT-DNA gene transfer in vivo. These results show that SBD-like PT-DNA readers exist widely in prokaryotes.