The intratumor microenvironment shapes the metastatic potential of cancer cells and their susceptibility to any immune response. Yet, the nature of the signals within the microenvironment that control anticancer immunity and how they are regulated is poorly understood. Here, using melanoma as a model, we investigate the involvement in metastatic dissemination and the immune-modulatory microenvironment of Protein S-Acyl Transferases as an underexplored class of potential therapeutic targets. We find that ZDHHC13 suppresses metastatic dissemination by palmitoylation of CTNND1, leading to stabilization of E-cadherin. Importantly, ZDHHC13 also reshapes the tumor immune microenvironment by suppressing lysophosphatidylcholine (LPC) synthesis in melanoma cells, leading to inhibition of M2-like tumor-associated macrophages that we show degrade E-cadherin via MMP12 expression. Consequently, ZDHHC13 activity suppresses tumor growth and metastasis in immunocompetent mice. Our study highlights the therapeutic potential of targeting the ZDHHC13-E-cadherin axis and its downstream metabolic and immune-modulatory mechanisms, offering additional strategies to inhibit melanoma progression and metastasis.