Lysine methylation is a classic posttranslational modification (PTM), but the major studies focus on histone methylation. Although emerging evidence demonstrates the significance of nonhistone lysine methylation, current method by investigation of each individual protein of interest is rather low throughput. Proteomics is an ideal strategy to study cellular PTM comprehensively, but current enrichment methods only allow identification of a few hundreds of methyllysine sites, due to insufficient affinity to low abundant tryptic peptides with methyllysine. Here we report a new method for lysine methylation profiling by covalent enrichment-enhanced proteomics, termed DEKmeP. Identification of over ten thousand methyllysine sites was achieved and thus this method provides a generalizable platform for deep and quantitative comparison of lysine methylation among different sets of cells by mass spectrometry. In practice, we identified numerous novel substrates of known active lysine methyltransferases (KMTs) and revealed brand new methyllysine sites by orphan KMTs. Moreover, we uncovered biological functions associated with new lysine methylation as a case of transcription factor c-Jun. Therefore, DEKmeP may change study style from focus on individual proteins of interest to systematic exploration of the methyllysine proteome, thereby expanding landscape of KMT catalysis and nonhistone lysine methylation to a new episode.