SETD3 is a member of the SET (Su(var)3–9, Enhancer of zeste, and Trithorax) domain protein superfamily and plays important roles in hypoxic pulmonary hypertension, muscle differentiation, and carcinogenesis. Previously, we identified SETD3 as the actin-specific methyltransferase that methylates the N3 of His73 on β-actin (Kwiatkowski et al., 2018). Here, we present two structures of S-adenosyl-L-homocysteine-bound SETD3 in complex with either an unmodified β-actin peptide or its His-methylated variant. Structural analyses, supported by biochemical experiments and enzyme activity assays, indicate that the recognition and methylation of β-actin by SETD3 are highly sequence specific, and that both SETD3 and β-actin adopt pronounced conformational changes upon binding to each other. In conclusion, this study is the first to show a catalytic mechanism of SETD3-mediated histidine methylation on β-actin, which not only throws light on the protein histidine methylation phenomenon but also facilitates the design of small molecule inhibitors of SETD3.