Melanoma is the most aggressive type of skin cancer in the United States with an increasing incidence. Melanoma lesions often exhibit high immunogenicity, with infiltrating immune cells playing important roles in regression of tumors occurring spontaneously or caused by therapeutic treatment. Computational and experimental methods have been used to estimate the abundance of immune cells in tumors, but their applications are limited by the requirement of large gene sets or multiple antibodies. Although the prognostic role of immune cells has been appreciated, a systematic investigation of their association with clinical factors, genomic features, prognosis and treatment response in melanoma is still lacking. This study, identifies a 25-gene signature based on RNA-seq data from The Cancer Genome Atlas (TCGA)-Skin Cutaneous Melanoma (TCGA-SKCM) dataset. This signature was used to calculate sample-specific Leukocyte Infiltration Scores (LIS) in six independent melanoma microarray datasets and scores were found to vary substantially between different melanoma lesion sites and molecular subtypes. For metastatic melanoma, LIS was prognostic in all datasets with high LIS being associated with good survival. The current approach provided additional prognostic information over established clinical factors, including age, tumor stage, and gender. In addition, LIS was predictive of patient survival in stage III melanoma, and treatment efficacy of tumor-specific antigen vaccine. IMPLICATIONS: This study identifies a 25-gene signature that effectively estimates the level of immune cell infiltration in melanoma, which provides a robust biomarker for predicting patient prognosis.