Despite success with BRAFV600E inhibitors, therapeutic responses in patients with metastatic melanoma are short-lived because of the acquisition of drug resistance. We identified a mechanism of intrinsic multidrug resistance based on the survival of a tumor cell subpopulation. Treatment with various drugs, including cisplatin and vemurafenib, uniformly leads to enrichment of slow-cycling, long-term tumor-maintaining melanoma cells expressing the H3K4-demethylase JARID1B/KDM5B/PLU-1. Proteome-profiling revealed an upregulation in enzymes of mitochondrial oxidative-ATP-synthesis (oxidative phosphorylation) in this subpopulation. Inhibition of mitochondrial respiration blocked the emergence of the JARID1B^high subpopulation and sensitized melanoma cells to therapy, independent of their genotype. Our findings support a two-tiered approach combining anticancer agents that eliminate rapidly proliferating melanoma cells with inhibitors of the drug-resistant slow-cycling subpopulation.