Melanomas are particularly renowned for their plasticity in response to microenvironmental signals. Uncovering organ-specific regulation of melanoma plasticity is important in developing anti-metastatic therapy aimed to tackle issues of resistance and evasiveness. The aim of our study was to reveal characteristics of metastatic growth of malignant melanoma in different anatomical sites, particularly brain, by in vivo imaging, cellular characterization and molecular approaches. The study was based on experimental metastasis models in vivo established from melanoma cell lines, Melmet 1 and Melmet 5 with opposing phenotypes (invasive/proliferative, respectively) in the in vitro setting. In vivo imaging indicated that Melmet 5 establishes metastases in multiple organs and at a faster rate than Melmet 1, which preferred the brain. Gene expression profiling of melanoma cells isolated from different metastatic growth phases, revealed a dynamic nature of the phenotypes transitioning from an invasive gene signature to a proliferative signature as the metastases passed from early to late phase. The presence of a molecular signature characteristic of neural cells in melanoma from brain metastases indicates activation of neurogenetic transcriptional programs. The neural-like signature was more pronounced in early versus late phase. To uncover microenvironmental factors that could stimulate reprogramming of melanoma cells, we analyzed gene expression in stroma cells from metastatic versus healthy brain. Genes implicated in immune-/inflammatory-response were up-regulated, suggesting an involvement of immunity-related cells. Indeed, cellular characterization of metastatic brain tissue revealed the emergence and accumulation of cells of bone-marrow origin like microglia (F4/80+, CD11b+) that correlated with “active growth” phase initiation. Altogether, this suggests that acquisition of the neuronal-invasive phenotype might be critical for the establishment of metastatic growth in the brain microenvironment. Host factors that appear to be involved in creating a permissive microenvironmental niche for melanoma cells to express such a neuronal-invasive phenotype, may represent focal points for targeting metastasis.