N-terminal methylation of free α-amino-groups is a post-translational modification of proteins that has been known for 30 years but has been very little studied. In this modification, the initiating M residue is cleaved and the exposed α-amino group is mono- di- or trimethylated by NRMT, a recently identified N-terminal methyltransferase. Currently, all known eukaryotic α-aminomethylated proteins have a unique N-terminal motif, M-X-P-K, where X is A, P, or S. NRMT can also methylate artificial substrates in vitro in which X is G, F, Y, C, M, K, R, N, Q or H. Methylation efficiencies of N-terminal amino acids are variable with respect to the identity of X. Here we use in vitro peptide methylation assays and substrate immunoprecipitations to show that the canonical M-X-P-K methylation motif is not the only one recognized by NRMT. We predict that N-terminal methylation is a widespread post-translational modification, and that there is interplay between N-terminal acetylation and N-terminal methylation. We also use isothermal calorimetry experiments to demonstrate that NRMT can efficiently recognize and bind to its fully methylated products.