Fatty acid uptake and altered metabolism constitute hallmarks of metastasis, yet evidence of the underlying biology, as well as whether all dietary fatty acids are prometastatic, is lacking. Here we show that dietary palmitic acid (PA), but not oleic acid or linoleic acid, promotes metastasis in oral carcinomas and melanoma in mice. Tumours from mice that were fed a short-term palm-oil-rich diet (PA), or tumour cells that were briefly exposed to PA in vitro, remained highly metastatic even after being serially transplanted (without further exposure to high levels of PA). This PA-induced prometastatic memory requires the fatty acid transporter CD36 and is associated with the stable deposition of histone H3 lysine 4 trimethylation by the methyltransferase Set1A (as part of the COMPASS complex (Set1A/COMPASS)). Bulk, single-cell and positional RNA-sequencing analyses indicate that genes with this prometastatic memory predominantly relate to a neural signature that stimulates intratumoural Schwann cells and innervation, two parameters that are strongly correlated with metastasis but are aetiologically poorly understood. Mechanistically, tumour-associated Schwann cells secrete a specialized proregenerative extracellular matrix, the ablation of which inhibits metastasis initiation. Both the PA-induced memory of this proneural signature and its long-term boost in metastasis require the transcription factor EGR2 and the glial-cell-stimulating peptide galanin. In summary, we provide evidence that a dietary metabolite induces stable transcriptional and chromatin changes that lead to a long-term stimulation of metastasis, and that this is related to a proregenerative state of tumour-activated Schwann cells.