Metastatic melanoma has poor prognosis and is refractory to most conventional chemotherapies. The alkylating agent temozolomide (TMZ) is commonly used in treating melanoma but has a disappointing response rate. Agents that can act cooperatively with TMZ and improve its efficacy are thus highly sought after. The BH3 mimetic ABT-737, which can induce apoptosis by targeting pro-survival Bcl-2 family members, has been found to enhance the efficacy of many conventional chemotherapeutic agents in multiple cancers. We found that combining TMZ and ABT-737 induced strong synergistic apoptosis in multiple human melanoma cell lines. When the drugs were used in combination in a mouse xenograft model, they drastically reduced tumor growth at concentrations where each individual drug had no significant effect. We found that TMZ treatment elevated p53 levels, and that the pro-apoptotic protein Noxa was elevated in TMZ/ABT-737 treated cells. Experiments with shRNA demonstrated that the synergistic effect of TMZ and ABT-737 was largely dependent on Noxa. Experiments with nutlin-3, a p53 inducer, demonstrated that p53 induction was sufficient for synergistic cell death with ABT-737 in a Noxa-dependent fashion. However, p53 was not necessary for TMZ/ABT-737 synergy as demonstrated by a p53-null line, indicating that TMZ and ABT-737 together induce Noxa in a p53-independent fashion. These results demonstrate that targeting anti-apoptotic Bcl-2 members is a promising method for treating metastatic melanoma, and that clinical trials with TMZ and Bcl-2 inhibitors are warranted.