MICA is a major histocompatibility complex-like protein that undergoes a structural transition from disorder to order upon binding its immunoreceptor, NKG2D. We redesigned the disordered region of MICA with RosettaDesign to increase NKG2D binding. Mutations that stabilize this region were expected to increase association kinetics without changing dissociation kinetics, increase affinity of interaction, and reduce entropy loss upon binding. MICA mutants were stable in solution, and they were amenable to surface plasmon resonance evaluation of NKG2D binding kinetics and thermodynamics. Several MICA mutants bound NKG2D with enhanced affinity, kinetic changes were primarily observed during association, and thermodynamic changes in entropy were as expected. However, none of the 15 combinations of mutations predicted to stabilize the receptor-bound MICA conformation enhanced NKG2D affinity, whereas all 10 mutants predicted to be destabilized bound NKG2D with increased on-rates. Five of these had affinities enhanced by 0.9-1.8 kcal/mol over wild type by one to three non-contacting substitutions. Therefore, in this case, mutations designed to mildly destabilize a protein enhanced association and affinity.