During the last decade, we saw an explosion of studies investigating the role of lysine methylation/demethylation of histones and non-histone proteins, such as p53, NF-kappaB, and E2F1. These ‘Ying-Yang’ post-translational modifications are important to fine-tuning the activity of these proteins. Lysine methylation and demethylation are catalyzed by protein lysine methyltransferases (PKMTs) and protein lysine demethylases (PKDMs). PKMTs, PKDMs, and their substrates have been shown to play important roles in cancers. Although the underlying mechanisms of tumorigenesis are still largely unknown, growing evidence is starting to link aberrant regulation of methylation to tumorigenesis. This review focuses on summarizing the recent progress in understanding of the function of protein lysine methylation, and in the discovery of small molecule inhibitors for PKMTs and PKDMs. We also discuss the potential and the caveats of targeting protein lysine methylation for the treatment of cancer.