The physiological changes that occur immediately following cancer surgeries initiate a chain of events that ultimately result in a short pro-, followed by a prolonged anti-, inflammatory period. Natural Killer (NK) cells are severely affected during this period in the recovering cancer patient. NK cells play a crucial role in anti-tumour immunity because of their innate ability to differentiate between malignant versus normal cells. Therefore, an opportunity arises in the aftermath of cancer surgery for residual cancer cells, including distant metastases, to gain a foothold in the absence of NK cell surveillance. Here, we describe the post-operative environment and how the release of sympathetic stress-related factors (e.g., cortisol, prostaglandins, catecholamines), anti-inflammatory cytokines (e.g., IL-6, TGF-β), and myeloid derived suppressor cells, mediate NK cell dysfunction. A snapshot of current and recently completed clinical trials specifically addressing NK cell dysfunction post-surgery is also discussed. In collecting and summarizing results from these different aspects of the surgical stress response, a comprehensive view of the NK cell suppressive effects of surgery is presented. Peri-operative therapies to mitigate NK cell suppression in the post-operative period could improve curative outcomes following cancer surgery.