GAF domains are a large family of regulatory domains, and a subset are found associated with enzymes involved in cyclic nucleotide (cNMP) metabolism such as adenylyl cyclases and phosphodiesterases. CyaB2, an adenylyl cyclase from Anabaena, contains two GAF domains in tandem at the N-terminus and an adenylyl cyclase domain at the C-terminus. Cyclic AMP, but not cGMP, binding to the GAF domains of CyaB2 increases the activity of the cyclase domain leading to enhanced synthesis of cAMP. Here we show that the isolated GAFb domain of CyaB2 can bind both cAMP and cGMP, and enhanced specificity for cAMP is observed only when both the GAFa and the GAFb domains are present in tandem (GAFab domain). In silico docking and mutational analysis identified distinct residues important for interaction with either cAMP or cGMP in the GAFb domain. Structural changes associated with ligand binding to the GAF domains could not be detected by bioluminescence resonance energy transfer (BRET) experiments. However, amide hydrogen-deuterium exchange mass spectrometry (HDXMS) experiments provided insights into the structural basis for cAMP-induced allosteric regulation of the GAF domains, and differences in the changes induced by cAMP and cGMP binding to the GAF domain. Thus, our findings could allow the development of molecules that modulate the allosteric regulation by GAF domains present in pharmacologically relevant proteins.