Compared with folded structures, natively unfolded protein domains are over-represented in protein-protein and protein-DNA interactions. Such domains are common features of all colicins and are required for their translocation across the outer membrane of the target Escherichia coli cell. All of these domains bind to at least one periplasmic protein of the Tol or Ton family. Similar domains are found in Ton-dependent outer membrane transporters, indicating they may interact in a related manner. In this article we have studied binding of the colicin N translocation domain to its periplasmic receptor TolA, by fluorescence resonance energy transfer (FRET) using fluorescent probes attached to engineered cysteine residues and NMR techniques. The domain exhibits a random coil circular dichroism spectrum. However, FRET revealed that guanidinium hydrochloride denaturation caused increases in all measured intramolecular distances showing that, although natively unfolded, the domain is not extended. Furthermore NMR reported a compact hydrodynamic radius of 18 A. Nevertheless the FRET-derived distances changed upon binding to TolA indicating a significant structural rearrangement. Using 1H-15N NMR we show that, when bound, the peptide switches from a disordered state to an ordered state. The kinetics of binding and the associated structural change were measured by stopped-flow methods, and both events appear to occur simultaneously. The data therefore suggest that this molecular recognition involves the concerted binding and folding of a flexible but collapsed state.