Virally encoded microRNAs (miRNAs) have recently been discovered in herpesviruses. However, their biological roles are mostly unknown. We developed an algorithm for the prediction of miRNA targets and applied it to human cytomegalovirus miRNAs, resulting in the identification of the major histocompatibility complex class I–related chain B (MICB) gene as a top candidate target of hcmv-miR-UL112. MICB is a stress-induced ligand of the natural killer (NK) cell activating receptor NKG2D and is critical for the NK cell killing of virus-infected cells and tumor cells. We show that hcmv-miR-UL112 specifically down-regulates MICB expression during viral infection, leading to decreased binding of NKG2D and reduced killing by NK cells. Our results reveal a miRNA-based immunoevasion mechanism that appears to be exploited by human cytomegalovirus.