Epigenetic dysregulation has been implicated in a variety of pathological processes including carcinogenesis. A major group of enzymes that influence epigenetic modifications are lysine demethylases (KDMs) also known as “erasers” which remove methyl groups on lysine (K) amino acids of histones. Numerous studies have implicated aberrant lysine demethylase activity in a variety of cancers, including melanoma. This review will focus on the structure, classification and functions of KDMs in normal biology and the current knowledge of how KDMs are deregulated in cancer pathogenesis, emphasizing our interest in melanoma. We highlight the current knowledge gaps of KDMs in melanoma pathobiology and describe opportunities to increases our understanding of their importance in this disease. We summarize the progress of several pre-clinical compounds that inhibit KDMs and represent promising candidates for further investigation in oncology.