Natural products are important sources for drug discovery, especially anti-tumor drugs. β-Elemene, the prominent active ingredient extract from the rhizome of Curcuma wenyujin, is a representative natural product with broad anti-tumor activities. The main molecular mechanism of β-elemene is to inhibit tumor growth and proliferation, induce apoptosis, inhibit tumor cell invasion and metastasis, enhance the sensitivity of chemoradiotherapy, regulate the immune system, and reverse multidrug resistance (MDR). Elemene oral emulsion and elemene injection were approved by the China Food and Drug Administration (CFDA) for the treatment of various cancers and bone metastasis in 1994. However, the lipophilicity and low bioavailability limit its application. To discover better β-elemene-derived anti-tumor drugs with satisfying drug-like properties, researchers have modified its structure under the premise of not damaging the basic scaffold structure. In this review, we comprehensively discuss and summarize the potential anti-tumor mechanisms and the progress of structural modifications of β-elemene.