The chemotherapeutic agent temozolomide (TMZ) kills tumor cells preferentially via alkylation of the O6-position of guanine. However, cells that express the DNA repair enzyme O6-methylguanine-DNA methyltransferase (MGMT), or harbor deficient DNA mismatch repair (MMR) function, are profoundly resistant to this drug. TMZ is in clinical use for melanoma, but objective response rates are low, even when TMZ is combined with O6-benzylguanine (O6BG), a potent MGMT inhibitor. We used in vitro and in vivo models of melanoma to characterize the early events leading to cellular TMZ resistance. Melanoma cell lines were exposed to a single treatment with TMZ, at physiologically relevant concentrations, in the absence or presence of O6BG. Surviving clones and mass cultures were analyzed by Western blot, colony formation assays, and DNA methylation studies. Mice with melanoma xenografts received TMZ treatment, and tumor tissue was analyzed by immunohistochemistry. We found that MGMT-negative melanoma cell cultures, before any drug treatment, already harbored a small fraction of MGMT-positive cells, which survived TMZ treatment and promptly became the dominant cell type within the surviving population. The MGMT-negative status in individual cells was not stable, as clonal selection of MGMT-negative cells again resulted in a mixed population harboring MGMT-positive, TMZ-resistant cells. Blocking the survival advantage of MGMT via the addition of O6BG still resulted in surviving clones, although at much lower frequency and independent of MGMT, and the resistance mechanism of these clones was based on a common lack of expression of MSH6, a key MMR enzyme. TMZ treatment of mice implanted with MGMT-negative melanoma cells resulted in effective tumor growth delay, but eventually tumor growth resumed, with tumor tissue having become MGMT positive. Altogether, these data reveal stochastic expression of MGMT as a pre-existing, key determinant of TMZ resistance in melanoma cell lines. Although MGMT activity can effectively be eliminated by pharmacologic intervention with O6BG, additional layers of TMZ resistance, although considerably rarer, are present as well and minimize the cytotoxic impact of TMZ/O6BG combination treatment. Our results provide rational explanations regarding clinical observations, where the TMZ/O6BG regimen has yielded mostly disappointing outcomes in melanoma patients.