Ubiquitin-like modifications regulate nearly every aspect of cellular functions. A key step in these modifications is the recognition of the carrier enzyme (E2) by the activating enzyme (E1). In this study, we have found that a critical E2-binding surface on the E1 of the small ubiquitin-like modifier has unusually high populations in both ordered and disordered states. Upon binding the E2, the disordered state is converted to the ordered state, which resembles the structure of the bound conformation, providing a mechanism to resolve the "Levinthal Paradox" search problem in a folding-upon-binding process. The significance of the folding-unfolding equilibrium is shown by the loss of functions of the mutations that shift the equilibrium to the folded state. This study highlights the importance of conformational flexibility in the molecular recognition event.