Edema factor (EF), a key anthrax exotoxin, has an anthrax protective antigen-binding domain (PABD) and a calmodulin (CaM)-activated adenylyl cyclase domain. Here, we report the crystal structures of CaM-bound EF, revealing the architecture of EF PABD. CaM has N- and C-terminal domains and each domain can bind two calcium ions. Calcium binding induces the conformational change of CaM from closed to open. Structures of the EF-CaM complex show how EF locks the N-terminal domain of CaM into a closed conformation regardless of its calciumloading state. This represents a mechanism of how CaM effector alters the calcium affinity of CaM and uncouples the conformational change of CaM from calcium loading. Furthermore, structures of EF-CaM complexed with nucleotides show that EF uses two-metal-ion catalysis, a prevalent mechanism in DNA and RNA polymerases. A histidine (H351) further facilitates the catalysis of EF by activating a water to deprotonate 30OH of ATP. Mammalian adenylyl cyclases share no structural similarity with EF and they also use two-metal-ion catalysis, suggesting the catalytic mechanism-driven convergent evolution of two structurally diverse adenylyl cyclases.