The pathogen Bacillus anthracis uses the Sortase A (SrtA) enzyme to anchor proteins to its cell wall envelope during vegetative growth. To gain insight into the mechanism of protein attachment to the cell wall in B. anthracis we investigated the structure, backbone dynamics, and function of SrtA. The NMR structure of SrtA has been determined with a backbone coordinate precision of 0.40 +/- 0.07 A. SrtA possesses several novel features not previously observed in sortase enzymes including the presence of a structurally ordered amino terminus positioned within the active site and in contact with catalytically essential histidine residue (His(126)). We propose that this appendage, in combination with a unique flexible active site loop, mediates the recognition of lipid II, the second substrate to which proteins are attached during the anchoring reaction. pK(a) measurements indicate that His(126) is uncharged at physiological pH compatible with the enzyme operating through a "reverse protonation" mechanism. Interestingly, NMR relaxation measurements and the results of a model building study suggest that SrtA recognizes the LPXTG sorting signal through a lock-in-key mechanism in contrast to the prototypical SrtA enzyme from Staphylococcus aureus.