CMVs efficiently target MHC I molecules to avoid recognition by cytotoxic T cells. However, the lack of MHC I on the cell surface renders the infected cell susceptible to NK cell killing upon missing self recognition. To counter this, mouse CMV (MCMV) rescues some MHC I molecules to engage inhibitory Ly49 receptors. Here we identify a new viral protein, MATp1, that is essential for MHC I surface rescue. Rescued altered-self MHC I molecules show increased affinity to inhibitory Ly49 receptors, resulting in inhibition of NK cells despite substantially reduced MHC I surface levels. This enables the virus to evade recognition by licensed NK cells. During evolution, this novel viral immune evasion mechanism could have prompted the development of activating NK cell receptors that are specific for MATp1-modified altered-self MHC I molecules. Our study solves a long-standing conundrum of how MCMV avoids recognition by NK cells, unravels a fundamental new viral immune evasion mechanism, and demonstrates how this forced the evolution of virus-specific activating MHC I-restricted Ly49 receptors.