AKAP79/150 is essential for coordinating second messenger-responsive enzymes in processes including synaptic long-term depression. Ca2+ directly regulates AKAP79 through its effector calmodulin (CaM), but the molecular basis of this regulation was previously unknown. Here, we report that CaM recognizes a '1-4-7-8' pattern of hydrophobic amino acids starting at Trp79 in AKAP79. Cross-linking coupled to mass spectrometry assisted mapping of the interaction site. Removal of the CaM-binding sequence in AKAP79 prevents formation of a Ca2+-sensitive interface between AKAP79 and calcineurin, and increases resting cellular PKA phosphorylation. We determined a crystal structure of CaM bound to a peptide encompassing its binding site in AKAP79. CaM adopts a highly compact conformation in which its open Ca2+-activated C-lobe and closed N-lobe cooperate to recognize a mixed α/310 helix in AKAP79. The structure guided a bioinformatic screen to identify potential sites in other proteins that may employ similar motifs for interaction with CaM.