Melanoma is the most aggressive skin cancer in humans. One severe complication is the formation of brain metastasis, which requires extravasation of melanoma cells across the tight blood-brain barrier (BBB). Previously, VLA-4 has been assigned a role for the adhesive interaction of melanoma cells with non-BBB endothelial cells. However, the role of melanoma VLA-4 for breaching the BBB remained unknown. In this study, we used a mouse in vitro BBB model and imaged the shear resistant arrest of melanoma cells on the BBB. Similar to effector T cells, inflammatory conditions of the BBB increased the arrest of melanoma cells followed by a unique post-arrest behavior lacking immediate crawling. However, over time, melanoma cells intercalated into the BBB and compromised its barrier properties. Most importantly, antibody ablation of VLA-4 abrogated melanoma shear resistant arrest on and intercalation into the BBB and protected the BBB from barrier breakdown. A tissue microarray established from human brain metastasis revealed that indeed a majority of 92% of all human melanoma brain metastases stained VLA-4 positive. We propose VLA-4 as a target for the inhibition of brain metastasis formation in the context of personalized medicine identifying metastasizing VLA-4 positive melanoma.