The secreted semaphorin Sema3E controls cell migration and invasiveness in cancer cells. Sema3E-receptor, PlexinD1, is frequently upregulated in melanoma, breast, colon, ovarian and prostate cancers; however, the mechanisms underlying PlexinD1 upregulation and the downstream events elicited in tumor cells are still unclear. Here we show that the canonical RBPjk-dependent Notch signaling cascade controls PlexinD1 expression in primary endothelial and cancer cells. Transcriptional activation was studied by quantitative PCR and promoter activity reporter assays. We found that Notch ligands and constitutively activated intracellular forms of Notch receptors upregulated PlexinD1 expression; conversely RNAi-based knock-down, or pharmacological inhibition of Notch signaling by gamma-secretase inhibitors, downregulated PlexinD1 levels. Notably, both Notch1 and Notch3 expression positively correlates with PlexinD1 levels in prostate cancer, as well as in other tumor types. In prostate cancer cells, Sema3E-PlexinD1 axis was previously reported to regulate migration; however, implicated mechanisms were not elucidated. Here we show that in these cells PlexinD1 activity induces the expression of the transcription factor Slug, downregulates E-cadherin levels and enhances cell migration. Moreover, our mechanistic data identify PlexinD1 as a pivotal mediator of this signaling axis downstream of Notch in prostate cancer cells. In fact, on one hand, PlexinD1 is required to mediate cell migration and E-cadherin regulation elicited by Notch. On the other hand, PlexinD1 upregulation is sufficient to induce prostate cancer cell migration and metastatic potential in mice, leading to functional rescue in the absence of Notch. In sum, our work identifies PlexinD1 as a novel transcriptional target induced by Notch signaling, and reveals its role promoting prostate cancer cell migration and downregulating E-cadherin levels in Slug-dependent manner. Collectively, these findings suggest that Notch-PlexinD1 signaling axis may be targeted to impair prostate cancer cell invasiveness and metastasis.