A classical and well-established mechanism that enables cells to adapt to new and adverse conditions is the acquisition of beneficial genetic mutations. Much less is known about epigenetic mechanisms that allow cells to develop novel and adaptive phenotypes without altering their genetic blueprint. It has been recently proposed that histone modifications, such as heterochromatin-defining H3K9 methylation (H3K9me), normally reserved to maintain genome integrity, can be redistributed across the genome to establish new and potentially adaptive phenotypes. To uncover the dynamics of this process, we developed a precision engineered genetic approach to trigger H3K9me redistribution on-demand in fission yeast. This enabled us to trace genome-scale RNA and chromatin changes over time prior to and during adaptation in long-term continuous cultures. Establishing adaptive H3K9me occurs over remarkably slow time-scales relative to the initiating stress. During this time, we captured dynamic H3K9me redistribution events ultimately leading to cells converging on an optimal adaptive solution. Upon removal of stress, cells relax to new transcriptional and chromatin states rather than revert to their initial (ground) state, establishing a tunable memory for a future adaptive epigenetic response. Collectively, our tools uncover the slow kinetics of epigenetic adaptation that allow cells to search for and heritably encode adaptive solutions, with implications for drug resistance and response to infection.