While invasion and metastasis of tumour cells are the principle factor responsible for cancer related deaths, the mechanisms governing the process remain poorly defined. Moreover, phenotypic divergence of sub-populations of tumour cells is known to underpin alternative behaviors linked to tumour progression such as proliferation, survival and invasion. In the context of melanoma, heterogeneity between two transcription factors, BRN2 and MITF, has been associated with phenotypic switching between predominantly invasive and proliferative behaviors respectively. Epigenetic changes, in response to external cues, have been proposed to underpin this process, however the mechanism by which the phenotypic switch occurs is unclear. Here we report the identification of the NFIB transcription factor as a novel downstream effector of BRN2 function in melanoma cells linked to the migratory and invasive characteristics of these cells. Furthermore, the function of NFIB appears to drive an invasive phenotype through an epigenetic mechanism achieved via the upregulation of the polycomb group protein EZH2. A notable target of NFIB mediated up-regulation of EZH2 is decreased MITF expression, which further promotes a less proliferative, more invasive phenotype. Together our data reveal that NFIB has the ability to promote dynamic changes in the chromatin state of melanoma cells to facilitate migration, invasion and metastasis.