Brain metastases (BM) are the most common brain tumour in adults and are ten times more likely to develop than primary brain tumours. More than 20% of patients with cancer will develop BM with the three most common sources being primary cancers of the lung, breast, and melanoma. Unfortunately, current treatment options for BM do not effectively eradicate BM, with a mere median overall survival time of 12 months in treated patients. This indicates the need for better and more effective therapies against BM. Using patient-derived cell lines established from surgically removed brain metastatic tumours of lung-, breast- and melanoma-BM patients, we generated patient-derived orthotopic murine xenograft (PDX) models of lung-, breast-, and melanoma-BM. From these PDX models, we isolated a rare population of stem-like brain metastasis initiating cells (BMICs) we termed “pre-metastatic”, that had traveled from their primary/orthotopic tumours and lodged in the brain but had not yet developed into mature BM. Transcriptomic analyses performed on pre-metastatic and non-pre-metastatic BMICs from lung, breast and melanoma PDX models of BM, identified a set of deregulated genes exclusive only to pre-metastatic BMICs. Further analysis revealed HLA-G as being commonly up-regulated only during the pre-metastatic stage of the lung-, breast-, and melanoma-BM cascade. In vitro and in vivo analyses demonstrated that HLA-G knock-down reduced the proliferation and survival of BMICs from all BM cohorts, and attenuated the establishment of mature brain metastatic tumours, implying a crucial role for HLA-G in the formation of BM. Developing a therapeutic strategy that targets HLA-G in BM may prove effective at completely eliminating brain metastatic cells at an early stage of the BM cascade, thereby turning a fatal disease into an eminently more treatable one.