The nucleation-condensation mechanism represents a major paradigm to understand the folding process of many small globular proteins. Although substantial evidence has been acquired for this mechanism, it has remained very challenging to characterize the initial events leading to the formation of a folding nucleus. To achieve this goal, we used a combination of relaxation dispersion NMR spectroscopy and molecular dynamics simulations to determine ensembles of conformations corresponding to the denatured, transition, and native states in the folding of the activation domain of human procarboxypeptidase A2 (ADA2h). We found that the residues making up the folding nucleus tend to interact in the denatured state in a transient manner and not simultaneously, thereby forming incomplete and distorted versions of the folding nucleus. Only when all the contacts between these key residues are eventually formed can the protein reach the transition state and continue folding. Overall, our results elucidate the mechanism of formation of the folding nucleus of a protein and provide insights into how its folding rate can be modified during evolution by mutations that modulate the strength of the interactions between the residues forming the folding nucleus.