The acquisition of cell motility is an early step in melanoma metastasis. Here we use intravital imaging of signalling reporter cell-lines combined with genome-wide transcriptional analysis to define signalling pathways and genes associated with melanoma metastasis. Intravital imaging revealed heterogeneous cell behaviour in vivo:< 10% of cells were motile and both singly moving cells and streams of cells were observed. Motile melanoma cells had increased Notch-and SRF-dependent transcription. Subsequent genome-wide analysis identified an overlapping set of genes associated with high Notch and SRF activity. We identified EZH2, a histone methyltransferase in the Polycomb repressive complex 2, as a regulator of these genes. Heterogeneity of EZH2 levels is observed in melanoma models, and co-ordinated upregulation of genes positively regulated by EZH2 is associated with melanoma metastasis. EZH2 was also identified as regulating the amelanotic phenotype of motile cells in vivo by suppressing expression of the P-glycoprotein Oca2. Analysis of patient samples confirmed an inverse relationship between EZH2 levels and pigment. EZH2 targeting with siRNA and chemical inhibition reduced invasion in mouse and human melanoma cell lines. The EZH2-regulated genes KIF2C and KIF22 are required for melanoma cell invasion and important for lung colonization. We propose that heterogeneity in EZH2 levels leads to heterogeneous expression of a cohort of genes associated with motile behaviour including KIF2C and KIF22. EZH2-dependent increased expression of these genes promotes melanoma cell motility and early steps in metastasis.