Many virulence factors in gram-positive bacteria are covalently anchored to the cell-wall peptidoglycan by sortase enzymes, a group of widely distributed cysteine transpeptidases. The Staphylococcus aureus Sortase A protein (SrtA) is the archetypal member of the Sortase family and is activated by Ca2+, an adaptation that may facilitate host colonization as elevated concentrations of this ion are encountered in human tissue. Here we show that a single Ca2+ ion bound to an ordered pocket on SrtA allosterically activates catalysis by modulating both the structure and dynamics of a large active site loop. Detailed nitrogen-15 relaxation measurements indicate that Ca2+ may facilitate the adaptive recognition of the substrate by inducing slow micro- to millisecond time-scale dynamics in the active site. Interestingly, relaxation compensated Carr-Purcell-Meiboom-Gill experiments suggest that the time scale of these motions is directly correlated with ion binding. The results of site-directed mutagenesis indicate that this motional coupling is mediated by the side chain of Glu-171, which is positioned within the beta6/beta7 loop and shown to contribute to Ca2+ binding. The available structural and dynamics data are compatible with a loop closure model of Ca2+ activation, in which the beta6/beta7 loop fluctuates between a binding competent closed form that is stabilized by Ca2+, and an open, highly flexible state that removes key substrate contacting residues from the active site.