Vanicosides A and B are the esters of hydroxycinnamic acids with sucrose, occurring in a few plant species from the Polygonaceae family. So far, vanicosides A and B have not been evaluated for anticancer activity against human malignant melanoma. In this study, we tested these two natural products, isolated from Reynoutria sachalinensis rhizomes, against two human melanoma cell lines (amelanotic C32 cell line and melanotic A375 cell line, both bearing endogenous BRAFV600E mutation) and two normal human cell lines—keratinocytes (HaCaT) and the primary fibroblast line. Additionally, a molecular docking of vanicoside A and vanicoside B with selected targets involved in melanoma progression was performed. Cell viability was studied using an MTT assay. A RealTime-Glo™ Annexin V Apoptosis and Necrosis assay was used for monitoring programmed cell death (PCD). Vanicoside A demonstrated strong cytotoxicity against the amelanotic C32 cell line (viability of the C32 cell line was decreased to 55% after 72 h incubation with 5.0 µM of vanicoside A), significantly stronger than vanicoside B. This stronger cytotoxic activity can be attributed to an additional acetyl group in vanicoside A. No significant differences in the cytotoxicity of vanicosides were observed against the less sensitive A375 cell line. Moreover, vanicosides caused the death of melanoma cells at concentrations from 2.5 to 50 µM, without harming the primary fibroblast line. The keratinocyte cell line (HaCaT) was more sensitive to vanicosides than fibroblasts, showing a clear decrease in viability after incubation with 25 µM of vanicoside A as well as a significant phosphatidylserine (PS) exposure, but without a measurable cell death-associated fluorescence. Vanicosides induced an apoptotic death pathway in melanoma cell lines, but because of the initial loss of cell membrane integrity, an additional cell death mechanism might be involved like permeability transition pore (PTP)-mediated necrosis that needs to be explored in the future. Molecular docking indicated that both compounds bind to the active site of the BRAFV600E kinase and MEK-1 kinase; further experiments on their specific inhibitory activity of these targets should be considered.