Cytomegaloviruses (CMVs) are highly prevalent, persistent human pathogens that not only evade but also shape our immune responses. Natural killer (NK) cells play an important role in the control of CMV and CMVs have in turn developed a plethora of immunoevasion mechanisms targeting NK cells. This complex interplay can leave a long-lasting imprint on the immune system in general and affect responses toward other pathogens and vaccines. This review aims to provide an overview of NK cell biology and development, the manipulation of NK cells by CMVs and the potential impact of these evasion strategies on responses to vaccination.