Tumor aggressiveness and progression is highly dependent on the process of metastasis, regulated by the coordinated interplay of genetic and epigenetic mechanisms. Metastasis involves several steps of epithelial to mesenchymal transition (EMT), anoikis resistance, intra- and extravasation, and new tissue colonization. EMT is considered as the most critical process allowing cancer cells to switch their epithelial characteristics and acquire mesenchymal properties. Emerging evidence demonstrates that epigenetics mechanisms, DNA methylation, histone modifications, and non-coding RNAs participate in the widespread changes of gene expression that characterize the metastatic phenotype. At the chromatin level, active and repressive histone post-translational modifications (PTM) in association with pleiotropic transcription factors regulate pivotal genes involved in the initiation of the EMT process as well as in intravasation and anoikis resistance, playing a central role in the progression of tumors. Herein, we discuss the main epigenetic mechanisms associated with the different steps of metastatic process, focusing in particular on the prominent role of histone modifications and the modifying enzymes that mediate transcriptional regulation of genes associated with tumor progression. We further discuss the development of novel treatment strategies targeting the reversibility of histone modifications and highlight their importance in the future of cancer therapy.