The major cause of melanoma mortality is metastasis to distant organs, frequently to the brain. The microenvironment plays a critical role in tumourigenesis and metastasis. In order to treat or prevent metastasis, the interactions of disseminated tumor cells with the microenvironment at the metastatic organ have to be elucidated. However, the role of brain stromal cells in facilitating metastatic growth is poorly understood. Astrocytes are glial cells that function in repair and scarring of the brain following injury, in part via mediating neuroinflammation, but the role of astrocytes in melanoma brain metastasis is largely unresolved. Here we show that astrocytes can be reprogrammed by human brain-metastasizing melanoma cells (HBMMCs) to express pro-inflammatory factors, including the cytokine IL-23, which was highly expressed by metastases-associated astrocytes in vivo. Moreover, we show that the interactions between astrocytes and melanoma cells are reciprocal: paracrine signaling from astrocytes up-regulates the secretion of the matrix metalloproteinase MMP2 and enhances the invasiveness of HBMMCs. IL-23 was sufficient to increase melanoma cell invasion, and neutralizing antibodies to IL-23 could block this enhanced migration, implying a functional role for astrocyte-derived IL-23 in facilitating the progression of HBMMCs. Knocking down the expression of MMP2 in melanoma cells resulted in inhibition of IL-23-induced invasiveness. Thus, our study demonstrates that bidirectional signaling between melanoma cells and astrocytes results in the formation of a pro-inflammatory milieu in the brain, and in functional enhancement of the metastatic potential of disseminated melanoma cells.