Protein dynamics make important but poorly understood contributions to molecular recognition phenomena. To address this, we measure changes in fast protein dynamics that accompany the interaction of the arabinose-binding protein (ABP) with its ligand, d-galactose, using NMR relaxation and molecular dynamics simulation. These two approaches present an entirely consistent view of the dynamic changes that occur in the protein backbone upon ligand binding. Increases in the amplitude of motions are observed throughout the protein, with the exception of a few residues in the binding site, which show restriction of dynamics. These counter-intuitive results imply that a localised binding event causes a global increase in the extent of protein dynamics on the pico- to nanosecond timescale. This global dynamic change constitutes a substantial favourable entropic contribution to the free energy of ligand binding. These results suggest that the structure and dynamics of ABP may be adapted to exploit dynamic changes to reduce the entropic costs of binding.