In melanoma, transcriptional profiling has revealed multiple co-existing cell states, including proliferative versus invasive sub-populations that have been posited to represent a “go or grow” tradeoff. Both of these populations are maintained in tumors, but how they physically interact to promote metastasis is unknown. We demonstrate that these subpopulations form spatially structured heterotypic clusters that cooperate in the seeding of metastasis. We unexpectedly found that INV cells were tightly adherent to each other, and formed clusters with a rim of PRO cells. Intravital imaging demonstrated cooperation between these populations, in which the INV cells facilitated the spread of less metastatic PRO cells. We identified the TFAP2 neural crest transcription factor as a master regulator of both clustering and the PRO/INV states. Our data suggest a framework for the co-existence of these two divergent cell populations, in which differing cell states form heterotypic clusters that promote metastasis via cell-cell cooperation.