Melanoma is an increasingly common and potentially fatal malignancy of the skin and some mucous membranes. As no cure exists for metastatic disease, there is an urgent need for novel drugs. 2'-Deoxy-5-fluorouridylyl-(3'-5')-3'-C-ethynylcytidine [5-FdU(3'-5')ECyd] and 3'-C-ethynylcytidinylyl-(5' → 1-O)-2-O-octadecyl-sn-glycerylyl-(3-O → 5')-2'-deoxy-5-fluorouridine [ECyd-lipid-5-FdU] represent cytostatic active duplex drugs, which can be metabolized into various active antimetabolites. We evaluated the cytotoxicity of these heterodinucleoside phosphate analogs, their corresponding monomers ECyd and 5-FdU and combinations thereof on six metastatic melanoma cell lines and six ex vivo patient-derived melanoma cells in comparison to current standard cytostatic agents and the BRAF V600E inhibitor Vemurafenib. In vitro (real-time)-proliferation assays demonstrated that 5-FdU(3'-5')ECyd and ECyd-lipid-5-FdU had a high cytotoxic efficacy causing 75% melanoma cell death at concentrations in the nanomolar and micromolar range. Cytotoxicity was conducted by induction of DNA cleavage indicating apoptotic cells. Chicken embryotoxicity demonstrated that the duplex drugs were less toxic than 5-FdU at 0.01 μM. In vivo the duplex drug 5-FdU(3'-5')ECyd was efficacious in the murine LOX IMVI melanoma xenograph model on administration of 11.2 mg/kg/injection every fourth day. Both duplex drugs are promising novel cytostatic agents for the treatment of malignant melanoma meriting clinical evaluation.