Post-translational methylation plays a crucial role in regulating and optimizing protein function. Protein histidine methylation, occurring as the two isomers 1- and 3- methylhistidine (1MH and 3MH), was first reported five decades ago, but remains largely unexplored. Here we report that METTL9 is a broad-specificity methyltransferase (MTase) that mediates the formation of the majority of 1MH present in mouse and human proteomes. The minimal requirement for METTL9-catalyzed methylation is a His-x-His (HxH) motif, where "x" is preferably a small amino acid, allowing METTL9 to methylate a number of HxH-containing proteins. Here, we show that the immunomodulatory protein S100A9 and the NDUFB3 subunit of mitochondrial respiratory Complex I are methylated at HxH motif using MALDI-TOF MS.