Most anti-cancer drugs are derived from natural resources such as marine, microbial and botanical sources. Cutaneous malignant melanoma is the most aggressive form of skin cancer, with a high mortality rate. Various treatments for malignant melanoma are available, but due to the development of multi-drug resistance, current or emerging chemotherapies have a relatively low success rates. This emphasizes the importance of discovering new compounds that are both safe and effective against melanoma. In vitro testing of melanoma cell lines and murine melanoma models offers the opportunity for identifying mechanisms of action of plant derived compounds and extracts. Common anti-melanoma effects of natural compounds include potentiating apoptosis, inhibiting cell proliferation and inhibiting metastasis. There are different mechanisms and pathways responsible for anti-melanoma actions of medicinal compounds such as promotion of caspase activity, inhibition of angiogenesis and inhibition of the effects of tumor promoting proteins such as PI3-K, Bcl-2, STAT3 and MMPs. This review thus aims at providing an overview of anti-cancer compounds, derived from natural sources, that are currently used in cancer chemotherapies, or that have been reported to show anti-melanoma, or anti-skin cancer activities. Phytochemicals that are discussed in this review include flavonoids, carotenoids, terpenoids, vitamins, sulforaphane, some polyphenols and crude plant extracts.