The Ca2+-binding protein S100A4 interacts with the C terminus of nonmuscle myosin IIA (NMIIA) causing filament disassembly, which is correlated with an increased metastatic potential of tumor cells. Despite high sequence similarity of the three NMII isoforms, S100A4 discriminates against binding to NMIIB. We searched for structural determinants of this selectivity. Based on paralog scanning using phage display, we identified a single position as major determinant of isoform selectivity. Reciprocal single amino acid replacements showed that at position 1907 (NMIIA numbering), the NMIIA/NMIIC-specific alanine provides about 60-fold higher affinity than the NMIIB-specific asparagine. The structural background of this can be explained in part by a communication between the two consecutive α-helical binding segments. This communication is completely abolished by the Ala-to-Asn substitution. Mutual swapping of the disordered tailpieces only slightly affects the affinity of the NMII chimeras. Interestingly, we found that the tailpiece and position 1907 act in a nonadditive fashion. Finally, we also found that the higher stability of the C-terminal coiled-coil region of NMIIB also discriminates against interaction with S100A4. Our results clearly show that the isoform-selective binding of S100A4 is determined at multiple levels in the structure of the three NMII isoforms and the corresponding functional elements of NMII act synergistically with one another resulting in a complex interaction network. The experimental and in silico results suggest two divergent evolutionary pathways: NMIIA and NMIIB evolved to possess S100A4-dependent and -independent regulations, respectively.