Cutaneous malignant melanoma (hereafter called melanoma) is one of the most aggressive cancers with increasing incidence and mortality rates worldwide. In this study, we performed a systematic investigation of the tumor microenvironmental and genetic factors associated with melanoma to identify prognostic biomarkers for melanoma. We calculated the immune and stromal scores of melanoma patients from the Cancer Genome Atlas (TCGA) using the ESTIMATE algorithm and found that they were closely associated with patients' prognosis. Then the differentially expressed genes were obtained based on the immune and stromal scores, and prognostic immune-related genes further identified. Functional analysis and the protein-protein interaction network further revealed that these genes enriched in many immune-related biological processes. In addition, the abundance of six infiltrating immune cells was analyzed using prognostic immune-related genes by TIMER algorithm. The unsupervised clustering analysis using immune-cell proportions revealed eight clusters with distinct survival patterns, suggesting that dendritic cells were most abundant in the microenvironment and CD8 T cells and neutrophils were significantly related to patients' prognosis. Finally, we validated these genes in three independent cohorts from the Gene Expression Omnibus database. In conclusion, this study comprehensively analyzed the tumor microenvironment and identified prognostic immune-related biomarkers for melanoma.