Although the development of bone metastasis is a major detrimental event in prostate cancer, the molecular mechanisms responsible for bone homing and destruction remain largely unknown. Here we show that loss of miR-15 and miR-16 in cooperation with increased miR-21 expression promote prostate cancer spreading and bone lesions. This combination of microRNA endows bone-metastatic potential to prostate cancer cells. Concomitant loss of miR-15/miR-16 and gain of miR-21 aberrantly activate TGF-β and Hedgehog signaling, that mediate local invasion, distant bone marrow colonization and osteolysis by prostate cancer cells. These findings establish a new molecular circuitry for prostate cancer metastasis that was validated in patients' cohorts. Our data indicate a network of biomarkers and druggable pathways to improve patient treatment.