Complex karyotype acute myeloid leukemia (CK-AML) has a dismal outcome with current treatments, underscoring the need for new therapies. Here, we report synergistic anti-leukemic activity of the BCL-2 inhibitor venetoclax (Ven) and the asparaginase formulation Pegylated Crisantaspase (PegC) in CK-AML in vitro and in vivo. Ven-PegC combination inhibited growth of multiple AML cell lines and patient-derived primary CK-AML cells in vitro. In vivo, Ven-PegC showed potent reduction of leukemia burden and improved survival, compared with each agent alone, in a primary patient-derived CK-AML xenograft. Superiority of Ven-PegC, compared to single drugs, and, importantly, the clinically utilized Ven-azacitidine combination, was also demonstrated in vivo in CK-AML. We hypothesized that PegC-mediated plasma glutamine depletion inhibits 4EBP1 phosphorylation, decreases the expression of proteins such as MCL-1, whose translation is cap dependent, synergizing with the BCL-2 inhibitor Ven. Ven-PegC treatment decreased cellular MCL-1 protein levels in vitro by enhancing eIF4E-4EBP1 interaction on the cap-binding complex via glutamine depletion. In vivo, Ven-PegC treatment completely depleted plasma glutamine and asparagine and inhibited mRNA translation and cellular protein synthesis. Since this novel mechanistically-rationalized regimen combines two drugs already in use in acute leukemia treatment, we plan a clinical trial of the Ven-PegC combination in relapsed/refractory CK-AML.