While immune checkpoint-based immunotherapy (ICI) shows spectacular clinical results in cancer patients, only a subset of the these respond favorably to such treatment. Response to ICI is dictated by the integration of complex networks of cellular interactions between malignant and non-malignant cells. Although new insights into the mechanisms that modulate the pivotal anti-tumoral activity of cytotoxic T-cells (Tcy) have recently been gained, much of what we have learned is based on single-cell analyses of dissociated tumor samples; therefore, we lack critical information about the spatial distribution of the relevant cell types. Here, we used multiplexed immunohistochemistry to spatially characterize the immune landscape of metastatic melanoma from responders vs non-responders to ICI. By creating such high-dimensional pathology maps, we show that Tcy gradually evolve towards an exhausted phenotype as they approach and infiltrate the tumor. Moreover, our analysis revealed a key cellular interaction network that functionally links Tcy and PD-L1+ macrophages. Critically, mapping the respective spatial distribution of these two cell populations predict response to anti-PD-1 immunotherapy with high confidence. We conclude that baseline measurements of the spatial context should be integrated in the design of predictive biomarkers to identify patients likely to benefit from ICI.