Brain metastasis is the most common type of intracranial cancer and is the main cause of cancer-associated mortality. Brain metastasis mainly originates from lung cancer. Using a previously established in vitro brain metastatic model, we found that brain metastatic PC14PE6/LvBr4 cells exhibited higher expression of β-catenin and increased migratory activity than parental PC14PE6 cells. Knockdown of β-catenin dramatically suppressed the motility and invasiveness of PC14PE6/LvBr4 cells, indicating β-catenin is involved in controlling metastatic potential. Since β-catenin protein was increased without a significant change in its mRNA levels, the mechanism underlying increased β-catenin stability was investigated. We found that ubiquitin-specific protease 4 (USP4), recently identified as a β-catenin-specific deubiquitinylating enzyme, was highly expressed in PC14PE6/LvBr4 cells and involved in the increased stability of β-catenin protein. Similar to β-catenin knockdown, USP4-silenced PC14PE6/LvBr4 cells showed decreased migratory and invasive abilities. Moreover, knockdown of both USP4 and β-catenin inhibited clonogenicity and induced mesenchymal-epithelial transition by downregulating ZEB1 in PC14PE6/LvBr4 cells. Using bioluminescence imaging, we found that knockdown of USP4 suppressed brain metastasis in vivo and significantly increased overall survival and brain metastasis-free survival. Taken together, our results indicate that USP4 is a promising therapeutic target for brain metastasis in patients with lung adenocarcinoma.