Maternal embryonic leucine zipper kinase (MELK) is frequently overexpressed in cancer, but the role of MELK in cancer is still poorly understood. MELK was shown to have roles in many cancer-associated processes including tumor growth, chemotherapy resistance, and tumor recurrence. To determine whether the frequent overexpression of MELK can be exploited in therapy, we performed a high-throughput screen using a library of Saccharomyces cerevisiae mutants to identify genes whose functions become essential when MELK is overexpressed. We identified two such genes: LAG2 and HDA3. LAG2 encodes an inhibitor of the SCF ubiquitin-ligase complex, while HDA3 encodes a subunit of the HDA1 histone deacetylase complex. We find that one of these synthetic lethal interactions is conserved in mammalian cells, as inhibition of a human homolog of HDA3 (HDAC4) is synthetically toxic in MELK overexpression cells. Altogether, our work identified a novel potential drug target for tumors that overexpress MELK.