The calcium regulatory protein calmodulin (CaM) binds in a calcium-dependent manner to numerous target proteins. The calmodulin-binding domain (CaMBD) region of Nicotiana tabacum MAPK phosphatase has an amino acid sequence that does not resemble the CaMBD of any other known Ca(2+)-CaM-binding proteins. Using a unique fusion protein strategy, we have been able to obtain a high resolution solution structure of the complex of soybean Ca(2+)-CaM4 (SCaM4) and this CaMBD. Complete isotope labeling of both parts of the complex in the fusion protein greatly facilitated the structure determination by NMR. The 12-residue CaMBD region was found to bind exclusively to the C-lobe of SCaM4. A specific Trp and Leu side chain are utilized to facilitate strong binding through a novel "double anchor" motif. Moreover, the orientation of the helical peptide on the surface of Ca(2+)-SCaM4 is distinct from other known complexes. The N-lobe of Ca(2+)-SCaM4 in the complex remains free for additional interactions and could possibly act as a calcium-dependent adapter protein. Signaling through the MAPK pathway and increases in intracellular Ca(2+) are both hallmarks of the plant stress response, and our data support the notion that coordination of these responses may occur through the formation of a unique CaM-MAPK phosphatase multiprotein complex.