Melatonin is a hormone identified in plants and pineal glands of mammals and possesses diverse physiological functions. Fisetin is a bio-flavonoid widely found in plants and exerts antitumor activity in several types of human cancers. However, the combinational effect of melatonin and fisetin on antitumor activity, especially in melanoma treatment, remains unclear. Here, we tested the hypothesis that melatonin could enhance the antitumor activity of fisetin in melanoma cells and identified the underlying molecular mechanisms. The combinational treatment of melanoma cells with fisetin and melatonin significantly enhanced the inhibitions of cell viability, cell migration and clone formation, and the induction of apoptosis when compared with the treatment of fisetin alone. Moreover, such enhancement of antitumor effect by melatonin was found to be mediated through the modulation of the multiply signaling pathways in melanoma cells. The combinational treatment of fisetin with melatonin increased the cleavage of PARP proteins, triggered more release of cytochrome-c from the mitochondrial inter-membrane, enhanced the inhibition of COX-2 and iNOS expression, repressed the nuclear localization of p300 and NF-κB proteins, and abrogated the binding of NF-κB on COX-2 promoter. Thus, these results demonstrated that melatonin potentiated the anti-tumor effect of fisetin in melanoma cells by activating cytochrome-c-dependent apoptotic pathway and inhibiting COX-2/iNOS and NF-κB/p300 signaling pathways, and our study suggests the potential of such a combinational treatment of natural products in melanoma therapy.