The study of associations between two biomolecules is the key to understanding molecular function and recognition. Molecular function is often thought to be determined by underlying structures. Here, combining a single-molecule study of protein binding with an energy-landscape-inspired microscopic model, we found strong evidence that biomolecular recognition is determined by flexibilities in addition to structures. Our model is based on coarse-grained molecular dynamics on the residue level with the energy function biased toward the native binding structure (the Go model). With our model, the underlying free-energy landscape of the binding can be explored. There are two distinct conformational states at the free-energy minimum, one with partial folding of CBD itself and significant interface binding of CBD to Cdc42, and the other with native folding of CBD itself and native interface binding of CBD to Cdc42. This shows that the binding process proceeds with a significant interface binding of CBD with Cdc42 first, without a complete folding of CBD itself, and that binding and folding are then coupled to reach the native binding state. The single-molecule experimental finding of dynamic fluctuations among the loosely and closely bound conformational states can be identified with the theoretical, calculated free-energy minimum and explained quantitatively in the model as a result of binding associated with large conformational changes. The theoretical predictions identified certain key residues for binding that were consistent with mutational experiments. The combined study identified fundamental mechanisms and provided insights about designing and further exploring biomolecular recognition with large conformational changes.