S100A4, also known as mts1, is a member of the S100 family of Ca2+-binding proteins that is directly involved in tumor invasion and metastasis via interactions with specific protein targets, including nonmuscle myosin-IIA (MIIA). Human S100A4 binds two Ca2+ ions with the typical EF-hand exhibiting an affinity that is nearly 1 order of magnitude tighter than that of the pseudo-EF-hand. To examine how Ca2+ modifies the overall organization and structure of the protein, we determined the 1.7 A crystal structure of the human Ca2+-S100A4. Ca2+ binding induces a large reorientation of helix 3 in the typical EF-hand. This reorganization exposes a hydrophobic cleft that is comprised of residues from the hinge region,helix 3, and helix 4, which afford specific target recognition and binding. The Ca2+-dependent conformational change is required for S100A4 to bind peptide sequences derived from the C-terminal portion of the MIIA rod with submicromolar affinity. In addition, the level of binding of Ca2+ to both EF-hands increases by 1 order of magnitude in the presence of MIIA. NMR spectroscopy studies demonstrate that following titration with a MIIA peptide, the largest chemical shift perturbations and exchange broadening effects occur for residues in the hydrophobic pocket of Ca2+-S100A4. Most of these residues are not exposed in apo-S100A4 and explain the Ca2+ dependence of formation of theS100A4-MIIA complex. These studies provide the foundation for understanding S100A4 target recognition and may support the development of reagents that interfere with S100A4 function.