Decitabine, an epigenetic modifier that reactivates genes otherwise suppressed by DNA promoter methylation, is effective for some, but not all cancer patients, especially those with solid tumors. It is commonly recognized that to overcome resistance and improve outcome, treatment should be guided by tumor biology, which includes genotype, epigenotype, and gene expression profile. We therefore took an integrative approach to better understand melanoma cell response to clinically relevant dose of decitabine and identify complementary targets for combined therapy. We employed eight different melanoma cell strains, determined their growth, apoptotic and DNA damage responses to increasing doses of decitabine, and chose a low, clinically relevant drug dose to perform whole-genome differential gene expression, bioinformatic analysis, and protein validation studies. The data ruled out the DNA damage response, demonstrated the involvement of p21(Cip1) in a p53-independent manner, identified the TGFbeta pathway genes CLU and TGFBI as markers of sensitivity to decitabine and revealed an effect on histone modification as part of decitabine-induced gene expression. Mutation analysis and knockdown by siRNA implicated activated beta-catenin/MITF, but not BRAF, NRAS or PTEN mutations as a source for resistance. The importance of protein stability predicted from the results was validated by the synergistic effect of Bortezomib, a proteasome inhibitor, in enhancing the growth arrest of decitabine in otherwise resistant melanoma cells. Our integrative analysis show that improved therapy can be achieved by comprehensive analysis of cancer cells, identified biomarkers for patient’s selection and monitoring response, as well as targets for improved combination therapy.