Combining a single-molecule study of protein binding with a coarse grained molecular dynamics model including solvent (water molecules) effects, we find that biomolecular recognition is determined by flexibilities in addition to structures. Our single-molecule study shows that binding of CBD (a fragment of Wiskott-Aldrich syndrome protein) to Cdc42 involves bound and loosely bound states, which can be quantitatively explained in our model as a result of binding with large conformational changes. Our model identified certain key residues for binding consistent with mutational experiments. Our study reveals the role of flexibility and a new scenario of dimeric binding between the monomers: first bind and then fold.