Natural killer cell receptors (NKRs) monitor the expression of major histocompatibility class I (MHC-I) and stress molecules to detect unhealthy tissue, such as infected or tumor cells. The NKR gene family shows a remarkable genetic diversity, containing several genes encoding receptors with activating and inhibiting signaling, and varying in gene content and allelic polymorphism. The expansion of the NKR genes is species-specific, with different species evolving alternative expanded NKR genes, which encode structurally different proteins, yet perform comparable functions. So far, the biological function of this expansion within the NKR cluster has remained poorly understood. To study the evolution of NKRs, we have developed an agent-based model implementing a coevolutionary scenario between hosts and herpes-like viruses that are able to evade the immune response by downregulating the expression of MHC-I on the cell surface. We show that hosts evolve specific inhibitory NKRs, specialized to particular MHC-I alleles in the population. Viruses in our simulations readily evolve proteins mimicking the MHC molecules of their host, even in the absence of MHC-I downregulation. As a result, the NKR locus becomes polygenic and polymorphic, encoding both specific inhibiting and activating receptors to optimally protect the hosts from coevolving viruses.