Improving the affinity of a high-affinity protein-protein interaction is a challenging problem that has practical applications in the development of therapeutic biomolecules. We used a combination of structure-based computational methods to optimize the binding affinity of an antibody fragment to the I-domain of the integrin VLA1. Despite the already high affinity of the antibody (Kd approximately 7 nM) and the moderate resolution (2.8 A) of the starting crystal structure, the affinity was increased by an order of magnitude primarily through a decrease in the dissociation rate. We determined the crystal structure of a high-affinity quadruple mutant complex at 2.2 A. The structure shows that the design makes the predicted contacts. Structural evidence and mutagenesis experiments that probe a hydrogen bond network illustrate the importance of satisfying hydrogen bonding requirements while seeking higher-affinity mutations. The large and diverse set of interface mutations allowed refinement of the mutant binding affinity prediction protocol and improvement of the single-mutant success rate. Our results indicate that structure-based computational design can be successfully applied to further improve the binding of high-affinity antibodies.