Metastasis is a complex cascade of events involving a finely tuned interplay between malignant cells and multiple host factors. The transition from benign tumor growth to malignancy is manifested by the ability of tumor cells to traverse tissue barriers and invade surrounding tissues. Among a multitude of factors playing a role, the small calcium-binding protein S100A4 has been found to add to the invasive and metastatic capacity of cancer cells. However, the exact molecular function or mechanism by which S100A4 exerts its putative metastasis-promoting effects has not been fully elucidated, and the protein is most likely involved in several aspects of tumor progression. Several studies have recently described a direct interaction and/or reciprocal influence between S100A4 and the tumor suppressor protein p53. This corresponds to reports linking p53 to other S100-family members, especially S100B. The consequences are intriguing, connecting the metastasis-promoting protein S100A4 to the large set of important p53-mediated functions, with broad potential importance in cancer development and metastasis. In this review we emphasize the studies involving p53 and S100A4, elucidating and comparing reported results and conclusions.