Calmodulin is a central mediator of calcium-dependent signal transduction pathways and regulates the activity of a large number of diverse targets. Calcium-dependent interactions of calmodulin with regulated proteins are of generally high affinity but of quite variable thermodynamic origins. Here we investigate the influence of the binding of the calmodulin-binding domain of calmodulin kinase I on the fast internal dynamics of calcium-saturated calmodulin. NMR relaxation was used to probe motion on the backbone (viewed through the backbone amide NH group) and the side chains (viewed through methyl groups). The distribution of the amplitudes of side chain dynamics is trimodal. The microscopic details of side chain motion are compared with those of a thermodynamically and structurally similar complex of calmodulin with the calmodulin-binding domain of the smooth muscle myosin light chain kinase. While there are no significant differences in backbone dynamics and no net change in methyl-bearing side chain dynamics, a large redistribution of the amplitude of methyl dynamics is observed between the two complexes. The variation in dynamics was largely localized to the heterogeneously dynamic target-binding interface, suggesting that differential dynamics of the binding surface plays a functional role in the high-affinity binding interactions of calmodulin. These results begin to reveal a fundamental role for residual protein entropy in molecular recognition by calmodulin.