The culture supernatant from macrophages overexpressing TRIM59 has a cytotoxic effect on melanoma, but the mechanism remains unclear. To investigate whether deletion of TRIM59 in macrophages affects the metastatic potential of melanoma cells, we polarized control and TRIM59-deficient bone marrow-derived macrophages to the M2 phenotype and collected the respective conditioned media (CM). Exposure to CM from TRIM59-/--M2 cultures significantly promoted migration and invasion by B16-F0 and B16-F10 cells. Cytokine profiling indicated a ~15-fold increase in TNF-α production in CM from TRIM59-/--M2 cultures, and neutralizing TNF-α activity abrogated the referred stimulatory effects on cell motility. Transcriptome analysis revealed significant upregulation of MMP-9 and Madcam1 in melanoma cells exposed to TRIM59-/--M2 CM. Inhibitory experiments determined that these changes were also TNF-α-dependent and mediated by activation of ERK signaling. Independent knockdown of MMP9 and Madcam1 in B16-F10 cells impeded epithelial-mesenchymal transition and inhibited subcutaneous tumor growth and formation of metastatic lung nodules in vivo. These data suggest TRIM59 expression attenuates the tumor-promoting effect of tumor-associated macrophages, most of which resemble the M2 phenotype. Moreover, they highlight the relevance of TRIM59 in macrophages as a potential regulator of tumor metastasis and suggest TRIM59 could serve as a novel target for cancer immunotherapy.