DNA phosphorothioation is widespread among prokaryotes, and might function to restrict gene transfer among different kinds of bacteria. There has been little investigation into the structural mechanism of the DNA phosphorothioation process. DndA is a cysteine desulfurase which is involved in the first step of DNA phosphorothioation. In this study, we determined the crystal structure of Streptomyces lividans DndA in complex with its covalently bound cofactor PLP, to a resolution of 2.4 Å. Our structure reveals the molecular mechanism that DndA employs to recognize its cofactor PLP, and suggests the potential binding site for the substrate L-cysteine on DndA. In contrast to previously determined structures of cysteine desulfurases, the catalytic cysteine of DndA was found to reside on a β strand. This catalytic cysteine is very far away from the presumable location of the substrate, suggesting that a conformational change of DndA is required during the catalysis process to bring the catalytic cysteine close to the substrate cysteine. Moreover, our in vitro enzymatic assay results suggested that this conformational change is unlikely to be a simple result of random thermal motion, since moving the catalytic cysteine two residues forward or backward in the primary sequence completely disabled the cysteine desulfurase activity of DndA.