Repeat proteins are increasingly attracting much attention as alternative scaffolds to immunoglobulin antibodies due to their unique structural features. Nonetheless, engineering interaction interface and understanding molecular basis for affinity maturation of repeat proteins still remain a challenge. Here, we present a structure-based rational design of a repeat protein with high binding affinity for a target protein. As a model repeat protein, a Toll-like receptor4 (TLR4) decoy receptor composed of leucine-rich repeat (LRR) modules was used, and its interaction interface was rationally engineered to increase the binding affinity for myeloid differentiation protein 2 (MD2). Based on the complex crystal structure of the decoy receptor with MD2, we first designed single amino acid substitutions in the decoy receptor, and obtained three variants showing a binding affinity (K(D)) one-order of magnitude higher than the wild-type decoy receptor. The interacting modes and contributions of individual residues were elucidated by analyzing the crystal structures of the single variants. To further increase the binding affinity, single positive mutations were combined, and two double mutants were shown to have about 3000- and 565-fold higher binding affinities than the wild-type decoy receptor. Molecular dynamics simulations and energetic analysis indicate that an additive effect by two mutations occurring at nearby modules was the major contributor to the remarkable increase in the binding affinities.