Although natural killer (NK) cells play an important role in the control of melanoma, hypoxic stress in the tumor microen-vironment may impair NK-mediated tumor cell killing by mechanisms that are not fully understood. In this study, we investigated the effect of hypoxia on the expression and channel activity of connexin 43 (Cx43) in melanoma cells and its impact on their susceptibility to NK cell-mediated lysis. Our results demonstrated that hypoxic stress increases Cx43 expression in melanoma cells via hypoxia-inducible factor-1α (HIF-1α) transcriptional activity. Hypoxic cells displaying increased Cx43 expression were less susceptible to NK cell-mediated lysis compared with normoxic cells expressing a moderate level of Cx43. Conversely, when overexpressed in normoxic tumor cells, Cx43 improves their susceptibility to N cell-mediated killing. We show that the NK cell immune synapse formed with normoxic melanoma cells is more stable and contains a high level of gapjunctional Cx43 whereas that formed with hypoxic cells is less stable and contains a significant lower level of gap-junctional Cx43. We provide evidence that the activation of autophagy in hypoxic melanoma cells selectively degrades gap-junctional Cx43, leading to the destabilization of the immune synapse and the impairment of NK cell-mediated killing. Inhibition of autophagy by genetic or pharmacological approaches as well as expression of the non-degradable form of Cx43 significantly restore its accumulation at the immune synapse and improves N cell-mediated lysis of hypoxic melanoma cells. This study provides the first evidence that the hypoxic microenvironment negatively affects the immune surveillance of tumors by NK cells through the modulation of Cx43-mediated intercellular communications.