Anaplasma phagocytophilum, the causative agent of Human Granulocytic Anaplasmosis (HGA), is an obligately intracellular α-proteobacterium that is transmitted by Ixodes spp ticks. However, the pathogen is not transovarially transmitted between tick generations and therefore needs to survive in both a mammalian host and the arthropod vector to complete its life cycle. To adapt to different environments, pathogens rely on differential gene expression as well as the modification of proteins and other molecules. Random transposon mutagenesis of A. phagocytophilum resulted in an insertion within the coding region of an o-methyltransferase (omt) family 3 gene. In wild-type bacteria, expression of omt was up-regulated during binding to tick cells (ISE6) at 2 hr post-inoculation, but nearly absent by 4 hr p.i. Gene disruption reduced bacterial binding to ISE6 cells, and the mutant bacteria that were able to enter the cells were arrested in their replication and development. Analyses of the proteomes of wild-type versus mutant bacteria during binding to ISE6 cells identified Major Surface Protein 4 (Msp4), but also hypothetical protein APH_0406, as the most differentially methylated. Importantly, two glutamic acid residues (the targets of the OMT) were methyl-modified in wild-type Msp4, whereas a single asparagine (not a target of the OMT) was methylated in APH_0406. In vitro methylation assays demonstrated that recombinant OMT specifically methylated Msp4. Towards a greater understanding of the overall structure and catalytic activity of the OMT, we solved the apo (PDB_ID:4OA8), the S-adenosine homocystein-bound (PDB_ID:4OA5), the SAH-Mn2+ bound (PDB_ID:4PCA), and SAM- Mn2+ bound (PDB_ID:4PCL) X-ray crystal structures of the enzyme. Here, we characterized a mutation in A. phagocytophilum that affected the ability of the bacteria to productively infect cells from its natural vector. Nevertheless, due to the lack of complementation, we cannot rule out secondary mutations.