Calmodulin (CaM), a eukaryotic calcium sensor that regulates diverse biological activities, consists of N- and C-terminal globular domains (N-CaM and C-CaM, respectively). CaM serves as the activator of CyaA, a 188-kDa adenylyl cyclase toxin secreted by Bordetella pertussis, which is the etiologic agent for whooping cough. Upon insertion of the N-terminal adenylyl cyclase domain (ACD) of CyaA to its targeted eukaryotic cells, CaM binds to this domain tightly ( approximately 200 pm affinity). This interaction activates the adenylyl cyclase activity of CyaA, leading to a rise in intracellular cAMP levels to disrupt normal cellular signaling. We recently solved the structure of CyaA-ACD in complex with C-CaM to elucidate the mechanism of catalytic activation. However, the structure of the interface between N-CaM and CyaA, the formation of which contributes a 400-fold increase of binding affinity between CyaA and CaM, remains elusive. Here, we used site-directed mutations and molecular dynamic simulations to generate several working models of CaM-bound CyaA-ACD. The validity of these models was evaluated by disulfide bond cross-linking, point mutations, and fluorescence resonance energy transfer experiments. Our study reveals that a beta-hairpin region (amino acids 259-273) of CyaA-ACD likely makes contacts with the second calcium binding motif of the extended CaM. This mode of interaction differs from the interaction of N-CaM with anthrax edema factor, which binds N-CaM via its helical domain. Thus, two structurally conserved, bacterial adenylyl cyclase toxins have evolved to utilize distinct binding surfaces and modes of activation in their interaction with CaM, a highly conserved eukaryotic signaling protein.