An open question in aggressive cancers such as melanoma is how malignant cells can shift the immune system to pro-tumorigenic functions. Here we identify midkine (MDK) as a melanoma-secreted driver of an inflamed, but immune evasive, microenvironment that defines poor patient prognosis and resistance to immune checkpoint blockade. Mechanistically, MDK was found to control the transcriptome of melanoma cells, allowing for coordinated activation of nuclear factor-κB and downregulation of interferon-associated pathways. The resulting MDK-modulated secretome educated macrophages towards tolerant phenotypes that promoted CD8+ T cell dysfunction. In contrast, genetic targeting of MDK sensitized melanoma cells to anti-PD-1/anti-PD-L1 treatment. Emphasizing the translational relevance of these findings, the expression profile of MDK-depleted tumors was enriched in key indicators of a good response to immune checkpoint blockers in independent patient cohorts. Together, these data reveal that MDK acts as an internal modulator of autocrine and paracrine signals that maintain immune suppression in aggressive melanomas.