Among the methods used to unravel protein interaction surfaces, chemical cross-linking followed by identification of the cross-linked peptides by mass spectrometry has proven especially useful in dynamic and complex systems. During the signal recognition particle (SRP)-dependent targeting of proteins to the bacterial plasma membrane, the specific interaction between Ffh (the protein component of SRP) and FtsY (the SRP receptor) is known to be essential for the efficiency and fidelity of this process. In this work, we studied the Escherichia coli and Thermus aquaticus Ffh.FtsY complexes by using chemical cross-linking and tandem mass spectrometry to identify nine intermolecular cross-linked peptides. This information was used in conjunction with a previously undescribed model-building approach that combines geometric restraint optimization with macromolecular docking. The resulting model of the Ffh.FtsY complex is in good agreement with the crystal structure solved shortly thereafter. Intriguingly, four of the cross-linked pairs involve the M domain of Ffh, which is absent from the crystal structure, providing previously undocumented experimental evidence that the M domain is positioned in close proximity to the Ffh.FtsY interface in the complex.