The ability of NK cells to specifically recognize cells lacking expression of self-MHC class I molecules was discovered over 30 years ago. It provided the foundation for the “missing self” hypothesis. Research in the two past decades has contributed to a detailed understanding of the molecular mechanisms that determine the specificity and strength of NK cell-mediated “missing self” responses to tumor cells. However, in light of the recent remarkable breakthroughs in clinical cancer immunotherapy, the cytolytic potential of NK cells still remains largely untapped in clinical settings. There is abundant evidence demonstrating partial or complete loss of HLA class I expression in a wide spectrum of human tumor types. Such loss may result from immune selection of escape variants by tumor-specific CD8 T cells and has more recently also been linked to acquired resistance to checkpoint inhibition therapy. In the present review, we discuss the early predictions of the “missing self” hypothesis, its molecular basis and outline the potential for NK cell-based adoptive immunotherapy to convert checkpoint inhibitor therapy-resistant patients into clinical responders.