Abstract Relapse of acute myeloid leukemia (AML) after allogeneic bone marrow transplantation has been linked to immune evasion due to reduced expression of major histocompatibility complex class II (MHCII) genes through unknown mechanisms. In this work, we developed CORENODE, a computational algorithm for genome-wide transcription network decomposition that identified a transcription factor (TF) tetrad consisting of IRF8, MYB, MEF2C, and MEIS1, regulating MHCII expression in AML cells. We show that reduced MHCII expression at relapse is transcriptionally driven by combinatorial changes in the expression of these TFs, where MYB and IRF8 play major opposing roles, acting independently of the IFNγ/CIITA pathway. Beyond the MHCII genes, MYB and IRF8 antagonistically regulate a broad genetic program responsible for cytokine signaling and T-cell stimulation that displays reduced expression at relapse. A small number of cells with altered TF abundance and silenced MHCII expression are present at the time of initial leukemia diagnosis, likely contributing to eventual relapse. Significance: Our findings point to an adaptive transcriptional mechanism of AML evolution after allogeneic transplantation whereby combinatorial fluctuations of TF expression under immune pressure result in the selection of cells with a silenced T-cell stimulation program. This article is highlighted in the In This Issue feature, p. 369