The contribution of epigenetic dysregulation to metastasis remains understudied. Through a meta-analysis of gene expression datasets followed by a mini-screen, we identified Plant Homeodomain Finger protein 8 (PHF8), a histone demethylase of the Jumonji C protein family, as a previously unidentified prometastatic gene in melanoma. Loss- and gain-of-function approaches demonstrate that PHF8 promotes cell invasion without affecting proliferation in vitro and increases dissemination but not subcutaneous tumor growth in vivo, thus supporting its specific contribution to the acquisition of metastatic potential. PHF8 requires its histone demethylase activity to enhance melanoma cell invasion. Transcriptomic and epigenomic analyses revealed that PHF8 orchestrates a molecular program that directly controls the TGFβ signaling pathway and, as a consequence, melanoma invasion and metastasis. Our findings bring a mechanistic understanding of epigenetic regulation of metastatic fitness in cancer, which may pave the way for improved therapeutic interventions.