Melanoma is the most aggressive skin cancer; there is no cure in advanced stages. Identifying molecular participants in melanoma progression may provide useful diagnostic and therapeutic tools. FK506 binding protein 51 (FKBP51), an immunophilin with a relevant role in developmental stages, is highly expressed in melanoma and correlates with aggressiveness and therapy resistance. We hypothesized a role for FKBP51 in melanoma invasive behaviour. FKBP51 promoted activation of epithelial-to-mesenchymal transition (EMT) genes and improved melanoma cell migration and invasion. In addition, FKBP51 induced some melanoma stem cell (MCSC) genes. Purified MCSCs expressed high EMT genes levels, suggesting that genetic programs of EMT and MCSCs overlap. Immunohistochemistry of samples from patients showed intense FKBP51 nuclear signal and cytoplasmic positivity for the stem cell marker nestin in extravasating melanoma cells and metastatic brains. In addition, FKBP51 targeting by small interfering RNA (siRNA) prevented the massive metastatic substitution of liver and lung in a mouse model of experimental metastasis. The present study provides evidence that the genetic programs of cancer stemness and invasiveness overlap in melanoma, and that FKBP51 plays a pivotal role in sustaining such a program.