Melanoma is one of the most aggressive types of skin cancer, with significant heterogeneity in overall survival. Currently, tumor-node-metastasis (TNM) staging is insufficient to provide accurate survival prediction and appropriate treatment decision making for several types of tumors, such as those in melanoma patients. Therefore, the identification of more reliable prognosis biomarkers is urgently essential. Recent studies have shown that low immune cells infiltration is significantly associated with unfavorable clinical outcome in melanoma patients. Here we constructed a prognostic-related gene signature for melanoma risk stratification by quantifying the levels of several cancer hallmarks and identify the Wnt/β-catenin activation pathway as a primary risk factor for low tumor immunity. A series of bioinformatics and statistical methods were combined and applied to construct a Wnt-immune-related prognosis gene signature. With this gene signature, we computed risk scores for individual patients that can predict overall survival. To evaluate the robustness of the result, we validated the signature in multiple independent GEO datasets. Finally, an overall survival-related nomogram was established based on the gene signature and clinicopathological features. The Wnt-immune-related prognostic risk score could better predict overall survival compared with standard clinicopathological features. Our results provide a comprehensive map of the oncogene-immune-related gene signature that can serve as valuable biomarkers for better clinical decision making.