The cyclin-dependent kinase (Cdk) inhibitor p21Waf1/Cip1/Sdi1, important for p53-dependent cell cycle control, mediates G1/S arrest through inhibition of Cdks and possibly through inhibition of DNA replication. Cdk inhibition requires a sequence of approximately 60 amino acids within the p21 NH2 terminus. We show, using proteolytic mapping, circular dichroism spectropolarimetry, and nuclear magnetic resonance spectroscopy, that p21 and NH2-terminal fragments that are active as Cdk inhibitors lack stable secondary or tertiary structure in the free solution state. In sharp contrast to the disordered free state, however, the p21 NH2 terminus adopts an ordered stable conformation when bound to Cdk2, as shown directly by NMR spectroscopy. We have, thus, identified a striking disorder-order transition for p21 upon binding to one of its biological targets, Cdk2. This structural transition has profound implications in light of the ability of p21 to bind and inhibit a diverse family of cyclin-Cdk complexes, including cyclin A-Cdk2, cyclin E-Cdk2, and cyclin D-Cdk4. Our findings suggest that the flexibility, or disorder, of free p21 is associated with binding diversity and offer insights into the role for structural disorder in mediating binding specificity in biological systems. Further, these observations challenge the generally accepted view of proteins that stable secondary and tertiary structure are prerequisites for biological activity and suggest that a broader view of protein structure should be considered in the context of structure-activity relationships.