Mesenchymal stromal cells (MSC) can be exploited as cellular delivery vehicles for the enzymes converting non-toxic prodrugs to toxic substances. Because of their inherent chemoresistance, they exert potent bystander and antitumor effect. Here we show that the human adipose tissue-derived MSC expressing fusion yeast cytosine deaminase::uracil phosphoribosyltransferase (CD-MSC) in combination with 5-fluorocytosine (5FC) mediated a long-term tumor-free survival in the 83.3% of tumor-bearing animals. CD-MSC/5FC treatment induced cytotoxicity against model human melanoma cells EGFP-A375. Only 4% of the therapeutic CD-MSC cells eliminated >98.5% of the tumor cells in vitro. Long-term tumor-free survival was confirmed in 15 out of the 18 animals. However, repeatedly used CD-MSC/5FC therapeutic regimen generated more aggressive and metastatic variant of the melanoma cells EGFP-A375/Rel3. These cells derived from the refractory xenotransplants exhibited increased resistance to the CD-MSC/5FC treatment, altered cell adhesion, migration, tumorigenic and metastatic properties. However, long-term curative effect was achieved by the augmentation of the CD-MSC/5FC regimen along with the inhibition of c-Met/hepatocyte growth factor signaling axis in this aggressive melanoma derivative. In summary, the CD-MSC/5FC regimen can be regarded as a very effective antitumor approach to achieve long-term tumor-free survival as demonstrated on a mouse model of aggressive human melanoma xenografts.