Tumor–stroma interactions are critical for epithelial-derived tumors, and among the stromal cell types, cancer-associated fibroblasts (CAFs) exhibit multiple functions that fuel growth, dissemination, and drug resistance. However, these interactions remain insufficiently characterized in non-epithelial tumors such as malignant melanoma. We generated monocultures of melanoma cells and matching CAFs from patients’ metastatic lesions, distinguished by oncogenic drivers and immunoblotting of characteristic markers. RNA sequencing of CAFs revealed a homogenous epigenetic program that strongly resembled the signatures from epithelial cancers, including enrichment for an epithelial-to-mesenchymal transition (EMT). Melanoma CAFs in monoculture displayed robust invasive behavior while patient-derived melanoma monocultures showed very little invasiveness. Instead, melanoma cells showed increased invasion when co-cultured with CAFs. In turn, CAFs showed increased proliferation when exposed to melanoma conditioned media (CM), mediated in part by melanoma-secreted transforming growth factor-alpha that acted on CAFs via the epidermal growth factor receptor. This study provides evidence that bidirectional interactions between melanoma and CAFs regulate progression of metastatic melanoma. © 2016 John Wiley & Sons A/S. Published by John Wiley & Sons Ltd