Lysine methyltransferases are known to regulate diverse cellular processes. Through post-translationally methylating proteins, they can modulate protein-protein interactions. While numerous lysine methyltransferases have been discovered, the mechanisms by which they select their substrates remain largely uncharacterised. Some lysine methyltransferases recognise lysines within a specific linear sequence motif, however current techniques for characterisation of these motifs are laborious and time consuming. Here we have developed a mass spectrometry-based technique to elucidate methyltransferase substrate recognition motifs, which we have applied to yeast elongation factor methyltransferase 1 (Efm1). Firstly, peptides containing alanine substitutions around the target lysine are methylated by the methyltransferase in vitro and analysed by LC-MS/MS. The relative methylation of each peptide is quantified in order to determine important residues in the motif. Secondly, peptide mixtures representing all 20 amino acid substitutions at one important position in the motif are methylated in vitro by the methyltransferase and analysed by LC-MS/MS. Since methylation has the same mass shift as many different amino acid substitutions, a deuterated form of the methyl donor is used for this methylation reaction, conferring a unique mass shift of 17 Da to methylated peptides. The relative amount of methylation of all 20 amino acid substitutions can then be analysed in order to determine which amino acids are preferred or tolerated by the methyltransferase at a certain position within the motif. Lastly, this motif can then be searched across the proteome in order to identify potential new substrates of the methyltransferase. Application of this technique to yeast Efm1 revealed a core Y-K-X-G-G-I motif. Efm1 is only the second non-histone lysine methyltransferase to have its recognition motif elucidated, and its motif is uniquely hydrophobic among the described lysine methyltransferase motifs. This demonstrates the usefulness of this technique for the elucidation of substrate recognition motifs of methyltransferases and other protein-modifying enzymes.