Transcription factors are central components of the intracellular regulatory networks that control gene expression. An increasingly recognized phenomenon among human transcription factors is the formation of structure upon target binding. Here, we study the folding and binding of the pKID domain of CREB to the KIX domain of the co-activator CBP. Our simulations of a topology-based Gxc5x8d-type model predict a coupled folding and binding mechanism, and the existence of partially bound intermediates. From transition-path and Phi-value analyses, we find that the binding transition state resembles the unstructured state in solution, implying that CREB becomes structured only after committing to binding. A change of structure following binding is reminiscent of an induced-fit mechanism and contrasts with models in which binding occurs to pre-structured conformations that exist in the unbound state at equilibrium. Interestingly, increasing the amount of structure in the unbound pKID reduces the rate of binding, suggesting a fly-casting-like process. We find that the inclusion of attractive non-native interactions results in the formation of non-specific encounter complexes that enhance the on-rate of binding, but do not significantly change the binding mechanism. Our study helps explain how being unstructured can confer an advantage in protein target recognition. The simulations are in general agreement with the results of a recently reported nuclear magnetic resonance study, and aid in the interpretation of the experimental binding kinetics.