We redesigned residues on the surface of MICA, a protein that binds the homodimeric immunoreceptor NKG2D, to increase binding affinity with a series of rational, incremental changes. A fixed-backbone RosettaDesign protocol scored a set of initial mutations, which we tested by surface plasmon resonance for thermodynamics and kinetics of NKG2D binding, both singly and in combination. We combined the best four mutations at the surface with three affinity-enhancing mutations below the binding interface found with a previous design strategy. After curating design scores with three cross-validated tests, we found a linear relationship between free energy of binding and design score, and to a lesser extent, enthalpy and design score. Multiple mutants bound with substantial subadditivity, but in at least one case full additivity was observed when combining distant mutations. Altogether, combining the best mutations from the two strategies into a septuple mutant enhanced affinity by 50-fold, to 50 nM, demonstrating a simple, effective protocol for affinity enhancement.