Novel chemotherapeutic strategies for acute myeloid leukemia (AML) treatment are called for. We have recently demonstrated that the phenazine 5,10-dioxide natural products iodinin (3) and myxin (4) exhibit potent and hypoxia-selective cell death on MOLM-13 human AML cells, and that the N-oxide functionalities are pivotal for the cytotoxic activity. Very few structure-activity relationship studies dedicated to phenazine 5,10-dioxides exist on mammalian cell lines and the present work describes our efforts regarding in vitro lead optimizations of the natural compounds iodinin (3) and myxin (4). Prodrug strategies reveal carbamate side chains to be the optimal phenol-attached group. Derivatives with no oxygen-based substituent (-OH or -OCH3) in the 6th position of the phenazine skeleton upheld potency if alkyl or carbamate side chains were attached to the phenol in position 1. 7,8-Dihalogenated- and 7,8-dimethylated analogs of 1-hydroxyphenazine 5,10-dioxide (21) displayed increased cytotoxic potency in MOLM-13 cells compared to all the other compounds studied. On the other hand, dihalogenated compounds displayed high toxicity towards the cardiomyoblast H9c2 cell line, while MOLM-13 selectivity of the 7,8-dimethylated analogs were less affected. Further, a parallel artificial membrane permeability assay (PAMPA) demonstrated the majority of the synthesized compounds to penetrate cell membranes efficiently, which corresponded to their cytotoxic potency. This work enhances the understanding of the structural characteristics essential for the activity of phenazine 5,10-dioxides, rendering them promising chemotherapeutic agents.