Anserine (β-alanyl-N(Pi)-methyl-L-histidine), a methylated derivative of carnosine (β-alanyl-L-histidine), is an abundant constituent of vertebrate skeletal muscles. Although it has been suggested to serve as a proton buffer and radical scavenger, its physiological function remains mysterious. The formation of anserine is catalyzed by carnosine N-methyltransferase, recently identified in chicken as histamine N-methyltransferase-like (HNMT-like) protein. Although the HNMT-like gene is absent in mammalian genomes, the activity of carnosine N-methyltransferase was reported in most mammalian species. In the present investigation, we purified carnosine N-methyltransferase from rat muscles about 2600-fold. Three polypeptides of ∼ 45, 50, and 70 kDa coeluting with the enzyme activity were identified in the preparation. Mass spectrometry analysis of these polypeptides resulted in the identification of UPF0586 protein C9orf41 homolog as the only meaningful candidate. Rat UPF0586 and its yeast, chicken, and human orthologs were expressed in COS-7 cells and purified to homogeneity. Although all recombinant proteins catalyzed the formation of anserine, as confirmed by chromatographic and mass spectrometry analysis, rat UPF0586 was more active on carnosine than other orthologs. Confocal microscopy of HeLa cells expressing recombinant UPF5086 proteins revealed their presence in both cytosol and nucleus. Carnosine and Gly-His were the best substrates for all UPF0586 orthologs studied, although the enzymes also methylated other l-histidine-containing di- and tripeptides. Finally, cotransfection of COS-7 cells with rat or human UPF0586 and carnosine synthase transformed the cells into efficient anserine producers. We conclude that UPF0586 is mammalian carnosine N-methyltransferase and hypothesize that it may also serve as a peptide or protein methyltransferase in eukaryotes.