Protein folding and binding are analogous processes, in which the protein 'searches' for favourable intramolecular or intermolecular interactions on a funnelled energy landscape. Many eukaryotic proteins are disordered under physiological conditions, and fold into ordered structures only on binding to their cellular targets. The mechanism by which folding is coupled to binding is poorly understood, but it has been hypothesized on theoretical grounds that the binding kinetics may be enhanced by a 'fly-casting' effect, where the disordered protein binds weakly and non-specifically to its target and folds as it approaches the cognate binding site. Here we show, using NMR titrations and (15)N relaxation dispersion, that the phosphorylated kinase inducible activation domain (pKID) of the transcription factor CREB forms an ensemble of transient encounter complexes on binding to the KIX domain of the CREB binding protein. The encounter complexes are stabilized primarily by non-specific hydrophobic contacts, and evolve by way of an intermediate to the fully bound state without dissociation from KIX. The carboxy-terminal helix of pKID is only partially folded in the intermediate, and becomes stabilized by intermolecular interactions formed in the final bound state. Future applications of our method will provide new understanding of the molecular mechanisms by which intrinsically disordered proteins perform their diverse biological functions.