Fe-S clusters are critical metallocofactors required for cell function. Fe-S cluster biogenesis is carried out by assembly machinery consisting of multiple proteins. Fe-S cluster biogenesis proteins work together to mobilize sulfide and iron, form the nascent cluster, traffic the cluster to target metalloproteins, and regulate the assembly machinery in response to cellular Fe-S cluster demand. A complex series of protein-protein interactions is required for the assembly machinery to function properly. Despite considerable progress in obtaining static three-dimensional structures of the assembly proteins, little is known about transient protein-protein interactions during cluster assembly or the role of protein dynamics in the cluster assembly process. The Escherichia coli cysteine desulfurase SufS (EC 18.104.22.168) and its accessory protein SufE work together to mobilize persulfide from L-cysteine, which is then donated to the SufB Fe-S cluster scaffold. Here we use amide hydrogen/deuterium exchange mass spectrometry (HDX-MS) to characterize SufS-SufE interactions and protein dynamics in solution. HDX-MS analysis shows that SufE binds near the SufS active site to accept persulfide from Cys-364. Furthermore, SufE binding initiates allosteric changes in other parts of the SufS structure that likely affect SufS catalysis and alter SufS monomer-monomer interactions. SufE enhances the initial l-cysteine substrate binding to SufS and formation of the external aldimine with pyridoxal phosphate required for early steps in SufS catalysis. Together, these results provide a new picture of the SufS-SufE sulfur transferase pathway and suggest a more active role for SufE in promoting the SufS cysteine desulfurase reaction for Fe-S cluster assembly.