HOXB13, a homeodomain transcription factor, is linked to recurrence following radical prostatectomy. While HOXB13 regulates Androgen Receptor (AR) functions in a context dependent manner, its critical effectors in prostate cancer (PC) metastasis remain largely unknown. To identify HOXB13 transcriptional targets in metastatic PCs, we performed integrative bioinformatics analysis of differentially expressed genes (DEGs) in the proximity of the human prostate tumor-specific AR binding sites. Unsupervised Principal Component Analysis (PCA) led to a focused core HOXB13 target gene-set referred to as HOTPAM9 (HOXB13 Targets separating Primary And Metastatic PCs). HOTPAM9 comprised 7 mitotic kinase genes overexpressed in metastatic PCs, TRPM8, and the heat shock protein HSPB8, whose levels were significantly lower in metastatic PCs compared to the primary disease. The expression of a two-gene set, CIT and HSPB8 with an overall balanced accuracy of 98.8% and a threshold value of 0.2347, was sufficient to classify metastasis. HSPB8 mRNA expression was significantly increased following HOXB13 depletion in multiple metastatic CRPC models. Increased expression of HSPB8 by the microtubule inhibitor Colchicine or by exogenous means suppressed migration of mCRPC cells. Collectively, our results indicate that HOXB13 promotes metastasis of PCs by coordinated regulation of mitotic kinases and blockade of a putative tumor suppressor gene.