Metastasis remains the most common cause of death in most cancers, with limited therapies for combating disseminated disease. While the primary tumor microenvironment is an important regulator of cancer progression, it is less well understood how different tissue environments influence metastasis. We analyzed tumor-stroma interactions that modulate organ tropism of brain, bone and lung metastasis in xenograft models. We identified a number of potential modulators of site-specific metastasis, including cathepsin S as a regulator of breast-to-brain metastasis. High cathepsin S expression at the primary site correlated with decreased brain metastasis-free survival in breast cancer patients. Both macrophages and tumor cells produce cathepsin S, and only the combined depletion significantly reduced brain metastasis in vivo. Cathepsin S specifically mediates blood-brain barrier transmigration via proteolytic processing of the junctional adhesion molecule (JAM)-B. Pharmacological inhibition of cathepsin S significantly reduced experimental brain metastasis, supporting its consideration as a therapeutic target for this disease.