Natural killer (NK) cells are circulating lymphocytes that play an important role in the control of viral infections and tumors. Their functions are regulated by several activating and inhibitory receptors. A subset of these receptors in human NK cells are the killer immunoglobulin-like receptors (KIRs), which interact with the highly polymorphic MHC class I molecules. One important function of NK cells is to detect cells that have down-regulated MHC expression (missing-self). Because MHC molecules have non polymorphic regions, their expression could have been monitored with a limited set of monomorphic receptors. Surprisingly, the KIR family has a remarkable genetic diversity, the function of which remains poorly understood. The mouse cytomegalovirus (MCMV) is able to evade NK cell responses by coding "decoy" molecules that mimic MHC class I. This interaction was suggested to have driven the evolution of novel NK cell receptors. Inspired by the MCMV system, we develop an agent-based model of a host population infected with viruses that are able to evolve MHC down-regulation and decoy molecules. Our simulations show that specific recognition of MHC class I molecules by inhibitory KIRs provides excellent protection against viruses evolving decoys, and that the diversity of inhibitory KIRs will subsequently evolve as a result of the required discrimination between host MHC molecules and decoy molecules.