MDA-9/Syntenin, a key scaffolding protein and a molecular hub involved in a diverse range of cell signaling responses, has proved to be a challenging target for the design and discovery of small molecule probes. In this paper, we report on the design and synthesis of small molecule ligands of this key protein. Genetic algorithm-based computational design and the five–eight step synthesis of three molecules led to ligands with affinities in the range of 1–3 µM, a 20–60-fold improvement over literature reports. The design and synthesis strategies, coupled with the structure-dependent gain or loss in affinity, afford the deduction of principles that should guide the design of advanced probes of MDA-9/Syntenin.