Hypoxia affects tumor aggressiveness and activates pathways associated with epithelial mesenchymal transition (EMT) which are crucial for tumor progress. In this study, the correlation of hypoxia and EMT with sentinel lymph node status and tumor-specific survival was investigated in primary melanomas. CD34 for capillary count and Hypoxia inducible factor-1α (HIF-1α) as hypoxia indicators as well as Ezrin and L1-Cell Adhesion Molecule (L1CAM), both critical proteins contributing to EMT, were analyzed using immunohistochemistry in 49 melanoma patients with long follow-up (F/U, mean 110 months; range 12–263 months). We found a significant correlation between Breslow tumor thickness and Ezrin expression (p = 0.018). L1CAM expression in primary melanoma was significantly associated with HIF-1α expression (p < 0.0001) and sentinel lymph node metastasis (p = 0.011). Furthermore, low capillary count, reflecting hypoxic condition, was significantly associated with Ezrin expression (p = 0.047) and decreased tumor-specific survival (p = 0.035). In addition, patients with high Ezrin expression in their primary melanoma had a dramatic loss of life early in their F/U period (mean survival time 29 months; range 15–44 month). Our results highlight the relevance of Ezrin, L1CAM and HIF-1α as prognostic markers in melanoma patients. Additionally, we demonstrate that hypoxia in primary melanoma affects EMT and is at least partly responsible for early metastatic dissemination.