Lysine methylation is a post-translational modification with emerging proteome-wide functions. Like its counterpart, arginine methylation, it is known to affect protein-protein interactions, and this has implications for its role in modulating the dynamics of protein-protein interaction networks. To uncover the mechanisms by which lysine methylation modulates protein-protein interactions, it is essential to discover and characterise the enzymes which catalyse methylation. Through mass spectrometry-based screening of knockouts of four putative yeast protein methyltransferases, we have discovered three novel lysine methyltransferases that methylate the translation elongation factor EF1α – YGR001C, YNL024C and YLR285W. YGR001C trimethylates lysine 79, YNL024C monomethylates lysine 390 and YLR285W is responsible for the di- and tri-methylation of two novel sites – lysines 3 and 5. All three methyltransferases belong to the seven-beta-strand family of methyltransferases, with YGR001C being previously putatively assigned as a N(6)-adenine-specific DNA methyltransferase. N6AMT2, the human homolog of YGR001C, is likely to also be a lysine methyltransferase, as lysine 79 is known to be trimethylated in human EF1α. The structural contexts of the modifications suggest that they may have distinct roles in modulating the function of EF1α. Besides its canonical role in facilitating delivery of tRNA to the ribosome, EF1α is known to have a number of so-called ‘moonlighting’ functions – including regulating the actin cytoskeleton and export of tRNA – which are facilitated by its numerous protein interaction partners. Understood in this context, it is likely that these methyltransferases serve to control which of the many protein-protein interactions EF1α partakes in, and thereby have proteome-wide functional implications.