Melanoma depends on, interacts with and reacts to the stroma in which it is embedded, including fibroblasts, extracellular matrix, endothelial cells and immune cells. However, the impact of melanoma on the epidermal tumor microenvironment—the multilayered epithelium of the skin—is poorly understood. Gap junctions are essential for intercellular communication and involved in proliferation, differentiation and homeostasis of keratinocytes. We have shown previously that the gap junction proteins connexin 26 and 30 (Cx26 and Cx30) are induced in the epidermal tumor microenvironment of skin cancers including melanoma. This study compares the extent of Cx26, Cx30 and Cx43 expression in the epidermal microenvironment of melanocytic nevi and melanomas and its association with melanoma thickness, proliferative index of the tumor and its microenvironment, and with 5-year metastasis and survival. We found that induction of Cx26 and Cx30 cell–cell border expression in the epidermal tumor microenvironment correlates to malignancy. Importantly, there was a significant correlation of tumor thickness with the vertical epidermal Cx26 and Cx30 expression pattern and the horizontal Cx26 dissemination. Furthermore, horizontal Cx26 expression correlated with metastasis. Vertical epidermal expression patterns of Cx26 and Cx30 significantly correlated with the proliferative index in the epidermal tumor microenvironment but not with the proliferative index in the tumor. In contrast, Cx43 did not correlate with malignancy, thickness or proliferative index. In summary, here we show for the first time a significant association between the progression of melanoma and alterations in its epithelial tumor microenvironment.