A major challenge for managing melanoma is its tumour-heterogeneity based on individual coexisting melanoma cell phenotypes. These phenotypes display variable responses to standard therapies and they drive individual steps of melanoma progression; hence understanding their behaviour is imperative. Melanoma phenotypes are defined by distinct transcriptional states, which relate to different melanocyte lineage development phases, ranging from a mesenchymal, neural crest-like to a proliferative, melanocytic phenotype. It is thought that adaptive phenotype plasticity based on transcriptional reprogramming drives melanoma progression, but at which stage individual phenotypes dominate and moreover, how they interact is poorly understood. We monitored melanocytic and mesenchymal phenotypes throughout melanoma progression and detected transcriptional reprogramming at different stages, with a gain in mesenchymal traits in circulating melanoma cells (CTCs) and proliferative features in metastatic tumours. Intriguingly, we found that distinct phenotype populations interact in a cooperative manner, which generates tumours of greater ‘fitness’, supports CTCs and expands organotropic cues in metastases. Fibronectin, expressed in mesenchymal cells, acts as key player in cooperativity and promotes survival of melanocytic cells. Our data reveal an important role for inter-phenotype communications at various stages of disease progression, suggesting these communications could act as therapeutic target.