Numerous proteins require cofactors to be active. Computer simulations suggest that cooperative interaction networks achieve optimal cofactor binding. There is a need for the experimental identification of the residues crucial for stabilizing these networks and thus for cofactor binding. Here we investigate the electron transporter flavodoxin, which contains flavin mononucleotide as non-covalently bound cofactor. We show that after binding flavin mononucleotide with nanomolar affinity, the protein relaxes extremely slowly (time constant ~5 days) to an energetically more favourable state with picomolar-binding affinity. Rare small-scale openings of this state are revealed through H/D exchange of N(3)H of flavin. We find that H/D exchange can pinpoint amino acids that cause tight cofactor binding. These hitherto unknown residues are dispersed throughout the structure, and many are located distantly from the flavin and seem irrelevant to flavodoxin's function. Quantification of the thermodynamics of ligand binding is important for understanding, engineering, designing and evolving ligand-binding proteins.