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 that mediates the formation of the majority of 1MH present in mouse and human proteomes. METTL9-catalyzed methylation requires a His-x-His (HxH) motif, where “x” is preferably a small amino acid, allowing METTL9 to methylate a number of HxH-containing proteins, including the immunomodulatory protein S100A9 and the NDUFB3 subunit of mitochondrial respiratory Complex I. Notably, METTL9-mediated methylation enhances respiration via Complex I, and the presence of 1MH in an HxH-containing peptide reduced its zinc binding affinity. Our results establish METTL9-mediated 1MH as a pervasive protein modification, thus setting the stage for further functional studies on protein histidine methylation.