Stage IV melanoma patients develop melanoma brain metastases (MBM) in 50% of cases. Their prognosis is improving, and its understanding outside the context of clinical trials is relevant. We have retrospectively analyzed the clinical data, course of treatment, and outcomes of 531 subsequent stage IV melanoma patients with BM treated in five reference Italian and Polish melanoma centers between 2014 and 2021. Patients with MBM after 2017 had a better prognosis, with a significantly improved median of overall survival (OS) after 2017 in the worst mol-GPA prognostic groups (mol-GPA ≤ 2): a median OS >6 months and HR 0.76 vs. those treated before 2017 (CI: 0.60–0.97, p = 0.027). In our prognostic model, mol-GPA was highly predictive for survival, and symptoms without steroid use did not have prognostic significance. Local therapy significantly improved survival regardless of the year of diagnosis (treated before or after 2017), with median survival >12 months. Systemic therapy improved outcomes when it was combined with local therapy. Local surgery was associated with improved OS regardless of the timing related to treatment start (i.e., before or after 30 days from MBM diagnosis). Local and systemic treatment significantly prolong survival for the poorest mol-GPA prognosis. Use of modern treatment modalities is justified in all mol-GPA prognostic groups.