Histone lysine methyltransferases (KMTs) are biomedically important epigenetic enzymes that catalyze the transfer of methyl group from S-adenosylmethionine to lysine’s nucleophilic ε-amino group in histone tails and core histones. Understanding the chemical basis of KMT catalysis is important for discerning its complex biology in disease, structure-function relationship, and for designing specific inhibitors with therapeutic potential. Here we examine histone peptides, which possess simplest lysine analogs with different nucleophilic character, as substrates for human KMTs. Combined MALDI-TOF MS experiments, NMR analyses and molecular dynamics and free-energy simulations based on quantum mechanics/molecular mechanics (QM/MM) potential provide experimental and theoretical evidence that KMTs do have an ability to catalyze methylation of primary amine-containing N-nucleophiles, but do not methylate related amide/guanidine-containing N-nucleophiles as well as simple O- and C-nucleophiles. The results demonstrate a broader, but still limited, substrate scope for KMT catalysis, and contribute to rational design of selective epigenetic inhibitors.