Despite the advent of immunotherapy, metastatic melanoma represents an aggressive tumor type with a poor survival outcome. The successful application of immunotherapy requires in-depth understanding of the biological basis and immunosuppressive mechanisms within the tumor microenvironment. In this study, we conducted spatially explicit analysis of the stromal-immune interface across 400 melanoma H&E specimens from TCGA (The Cancer Genome Atlas). A computational pathology pipeline (CRImage) was used to classify cells in the H&E specimen into stromal, immune or cancer cells. The estimated proportions of these cell types were validated by independent measures of tumor purity, pathologists' estimate of lymphocyte density, imputed immune cell subtypes and pathway analyses. Spatial interactions between these cell types were computed using a graph-based algorithm (Topological Tumor Graphs: TTGs). This approach identified two stromal features, namely stromal clustering and stromal barrier, which represented the melanoma stromal microenvironment. Tumors with increased stromal clustering and barrier were associated with reduced intratumoral lymphocyte distribution and poor overall survival independent of existing prognostic factors. To explore the genomic basis of these TTG-derived stromal phenotypes, we used a deep learning approach integrating genomic (copy number) and transcriptomic data, thereby inferring a compressed representation of copy number-driven alterations in gene expression. This integrative analysis revealed that tumors with high stromal clustering and barrier had reduced expression of pathways involved in naïve CD4 signalling, MAPK and PI3K signalling. Taken together, our findings support the immunosuppressive role of stromal cells within metastatic melanoma via physical barrier and T cell exclusion within the vicinity of cancer cells.