The membrane lipid phosphatidylcholine (PC) is crucial for stress adaptation and virulence of the plant pathogen Agrobacterium tumefaciens. The phospholipid N-methyltransferase PmtA catalyzes three successive methylations of phosphatidylethanolamine (PE) to yield PC. Here, we asked how PmtA is recruited to its site of action, the inner leaflet of the membrane. We found that the enzyme attaches to the membrane via electrostatic interactions with anionic lipids, which do not serve as substrate for PmtA. Increasing PC concentrations trigger membrane dissociation suggesting that membrane binding of PmtA is negatively regulated by its end product PC. Two predicted alpha-helical regions (A and F) contribute to membrane binding of PmtA. The N-terminal helix A binds anionic lipids in vitro with higher affinity than the central helix F. The latter undergoes a structural transition from disordered to -helical conformation in the presence of anionic lipids. The basic amino acids R8 and K12 and the hydrophobic amino acid F19 are critical for membrane binding by A as well as for activity of full-length PmtA. We conclude that a combination of electrostatic and hydrophobic forces is responsible for membrane association of the phospholipid-modifying enzyme.