Colicin N is a pore-forming bacteriocin that enters target Escherichia coli cells with the assistance of TolA, a protein in the periplasm of the target cell. The N-terminal domain of the colicin that carries the TolA-binding epitope, the translocation domain (T-domain), is intrinsically disordered. From (1)H-(13)C-(15)N NMR studies of isotopically labeled T-domain interacting with unlabeled TolAIII (the C-terminal domain of TolA), we have identified the TolA-binding epitope and have shown that the extent of its disorder is reduced on binding TolA, although it does not fold into a globular structure with defined secondary structure elements. Residues upstream and downstream of the 27-residue TolA-binding epitope remain disordered in the TolA-bound T-domain as they are in the free T-domain. Filamentous phage also exploits TolAIII to enter target cells, with TolAIII retaining its main secondary structure elements and global fold. In contrast to this, binding of the disordered T-domain of colicin A causes dramatic conformational changes in TolAIII marked by increased flexibility and lack of a rigid tertiary structure consistent with at least partial unfolding of TolAIII, suggesting that bacteriocins and bacteriophages parasitize E. coli using different modes of interaction with TolAIII. We have found that the colicin N T-domain-TolAIII interaction is strikingly similar to the previously described g3p-TolAIII interaction. The fact that both colicin N and filamentous phage exploit TolAIII in a similar manner, with one being a bacterial intrinsically disordered protein and the other being a viral structurally well-ordered protein, suggests that these represent a good example of convergent evolution at the molecular level.