p27 controls cell proliferation by binding and regulating nuclear cyclin-dependent kinases (CDKs). In addition, p27 interacts with other nuclear and cytoplasmic targets and has diverse biological functions. We seek to understand how the structural and dynamic properties of p27 mediate its several functions. We show that, despite showing disorder before binding its targets, p27 has nascent secondary structure that may have a function in molecular recognition. Binding to Cdk2-cyclin A is accompanied by p27 folding, and kinetic data suggest a sequential mechanism that is initiated by binding to cyclin A. p27 regulates CDK-cyclin complexes involved directly in cell cycle control and does not interact with other closely related CDKs. We show that p27-cyclin interactions are an important determinant of this specificity and propose that the homologous cell cycle regulators p21 and p57 function by a similar sequential, folding-on-binding mechanism.