Chronic Myeloid Leukemia (CML) represents 15-20% of all new cases of leukemia and is characterized by an uncontrolled proliferation of abnormal myeloid cells. Currently, the first-line of treatment involves Tyrosine Kinase Inhibitors (TKIs), which specifically inhibits the activity of the fusion protein BCR-ABL. However, resistance, mainly due to mutations, can occur. In the attempt to find more effective and less toxic therapies, several approaches are taken into consideration such as research of new anti-leukemic drugs and "combination chemotherapy" where different drugs that act by different mechanisms are used. Here, we reviewed the molecular mechanisms of CML, the main mechanisms of drug resistance and current strategies to enhance the therapeutic effect of TKIs in CML. Despite major advances in CML treatment, new, more potent anticancer drugs and with fewer side effects are needed. Marine organisms, and particularly seaweed, have a high diversity of bioactive compounds with some of them having anticancer activity in several in vitro and in vivo models. The state-of-art suggests that their use during cancer treatment may improve the outcome. We reviewed here the yet few data supporting anti-leukemic activity of some carotenoids and phlorotannins in some leukemia models. Also, strategies to overcome drug resistance are discussed, particularly the combination of conventional drugs with natural compounds.