Metastatic colonization of distant organs accounts for over 90% of deaths related to solid cancers, yet the molecular determinants of metastasis remain poorly understood. Here, we unveil a mechanism of colonization in the aggressive basal-like subtype of breast cancer that is driven by the NAD metabolic enzyme nicotinamide N-methyltransferase (NNMT). We demonstrate that NNMT imprints a basal genetic program into cancer cells, enhancing their plasticity. In line, NNMT expression is associated with poor clinical outcomes in patients with breast cancer. Accordingly, ablation of NNMT dramatically suppresses metastasis formation in pre-clinical mouse models. Mechanistically, NNMT depletion results in a methyl overflow that increases histone H3K9 trimethylation (H3K9me3) and DNA methylation at the promoters of PR/SET Domain-5 (PRDM5) and extracellular matrix-related genes. PRDM5 emerged in this study as a pro-metastatic gene acting via induction of cancer-cell intrinsic transcription of collagens. Depletion of PRDM5 in tumor cells decreases COL1A1 deposition and impairs metastatic colonization of the lungs. These findings reveal a critical activity of the NNMT-PRDM5-COL1A1 axis for cancer cell plasticity and metastasis in basal-like breast cancer.