Biological processes essentially all depend on the specific recognition between macromolecules and their interaction partners. Although many such interactions have been characterized both structurally and biophysically, the thermodynamic effects of small atomic changes remain poorly understood. Based on the crystal structure of the bacterial invasion protein internalin (InlA) of Listeria monocytogenes in complex with its human receptor E-cadherin (hEC1), we analyzed the interface to identify single amino acid substitutions in InlA that would potentially improve the overall quality of interaction and hence increase the weak binding affinity of the complex. Dissociation constants of InlA-variant/hEC1 complexes, as well as enthalpy and entropy of binding, were quantified by isothermal titration calorimetry. All single substitutions indeed significantly increase binding affinity. Structural changes were verified crystallographically at < or =2.0-A resolution, allowing thermodynamic characteristics of single substitutions to be rationalized structurally and providing unique insights into atomic contributions to binding enthalpy and entropy. Structural and thermodynamic data of all combinations of individual substitutions result in a thermodynamic network, allowing the source of cooperativity between distant recognition sites to be identified. One such pair of single substitutions improves affinity 5,000-fold. We thus demonstrate that rational reengineering of protein complexes is possible by making use of physically distant hot spots of recognition.