Cancer cells that are capable of surviving an initial drug exposure hold the potential for disease relapse in patients. Reports on distinct cancer types uniformly describe the existence of multi-drug tolerant highly tumorigenic cancer cell populations surviving diverse drug exposures. However their mode of formation and the dynamics leading to permanent resistance are poorly understood but are important to design better treatment strategies. Here we show that melanoma cells in general exhibit an early innate response as a primary survival reaction towards unfavourable environmental conditions or drug exposure, inducing a transition into multi-drug tolerant stem-like cells termed induced drug tolerant cells (IDTC), expressing markers like CD271, ABCB5 and high ALDH activity. This response comprises global chromatin remodelling through the modulation of histone methylation patterns of H3K4, H3K9 and H3K27, in turn leading to activation of multiple signalling cascades, and gain of high tumorigenic potency. IDTCs exhibit persistent rewiring capabilities of signalling cascades including ERK and AKT pathways making them a constantly varying target, thereby suggesting the need of alternative treatment strategies which might include drug holidays to prevent or delay the emergence of IDTCs and acquired drug resistance.