The crucial issue for defining successful natural killer (NK)-based anticancer therapy is the ability of tumor cells to activate resistance mechanisms leading to escape from NK-mediated killing. It is now well established that such mechanisms are likely evolved under hypoxia in the tumor microenvironment. Here, we show that hypoxia-induced autophagy impairs breast cancer cell susceptibility to NK-mediated lysis and that this impairment is reverted by targeting autophagy. We provide evidence that activation of autophagy in hypoxic cells is involved in selective degradation of the pro-apoptotic NK-derived serine protease GZMB/granzyme B, thereby blocking NK-mediated target cell apoptosis. Our in vivo data validate the concept that targeting autophagy in cancer cells promotes tumor regression by facilitating their elimination by NK cells. This study provides a cutting-edge advance in our understanding of how hypoxia-induced autophagy impairs NK-mediated lysis and might pave the way for formulating more effective NK-based antitumor therapy by combining autophagy inhibitors.