Bladder cancer (BLCa) metastasis is a predominant cause of death for bladder cancer patients. Histone demethylase KDM3A specifically removes the repressive mono- or di-methyl marks from H3K9 and thus contributes to the activation of gene transcription. However, the underlying mechanisms of KDM3A in bladder cancer are poorly understood. Here, we report that high levels of KDM3A are associated with bladder cancer clinical progression. KDM3A silencing inhibits bladder cancer cell growth, cell migration and invasion in vitro and in vivo. Mechanistically, we identify that non-classic deubiquitinase USP13 interacts with KDM3A to promote its degradation in cytoplasm via the proteasome-specific pathway. USP13 was significantly down-regulated in bladder cancer tissues and negatively associated with KDM3A expression. Furthermore, we show in bladder injected-liver metastasis xenograft model that USP13 inhibits bladder cancer metastasis through destabilizing cytoplasmic KDM3A. Collectively, our findings identify KDM3A is an important regulator of bladder cancer cell growth and metastasis and targeting USP13/KDM3A complex could be a valuable strategy to ameliorate bladder cancer progression and metastasis.