Cyclic nucleotides (cAMP and cGMP) regulate multiple intracellular processes and are thus of a great general interest for molecular and structural biologists. To study the allosteric mechanism of different cyclic nucleotide binding (CNB) domains, we compared cAMP-bound and cAMP-free structures (PKA, Epac, and two ionic channels) using a new bioinformatics method: local spatial pattern alignment. Our analysis highlights four major conserved structural motifs: 1) the phosphate binding cassette (PBC), which binds the cAMP ribose-phosphate, 2) the "hinge," a flexible helix, which contacts the PBC, 3) the beta(2,3) loop, which provides precise positioning of an invariant arginine from the PBC, and 4) a conserved structural element consisting of an N-terminal helix, an eight residue loop and the A-helix (N3A-motif). The PBC and the hinge were included in the previously reported allosteric model, whereas the definition of the beta(2,3) loop and the N3A-motif as conserved elements is novel. The N3A-motif is found in all cis-regulated CNB domains, and we present a model for an allosteric mechanism in these domains. Catabolite gene activator protein (CAP) represents a trans-regulated CNB domain family: it does not contain the N3A-motif, and its long range allosteric interactions are substantially different from the cis-regulated CNB domains.