Many advanced tumors overexpress and secrete the S100A4 protein that is known to promote angiogenesis and metastasis development. The mechanisms of this effect and the endothelial receptor for S100A4 are both still unknown. Here we report that extracellular S100A4 interacts with annexin II, an endothelial plasminogen co-receptor. Co-localization and direct binding of S100A4 and annexin II were demonstrated, and the binding site was identified in the N-terminal region of annexin II. S100A4 alone or in a complex with annexin II accelerated tissue plasminogen activator-mediated plasminogen activation in solution and on the endothelial cell surface through interaction of the S100A4 C-terminal lysines with the lysine-binding domains of plasminogen. A synthetic peptide corresponding to the N terminus of annexin II prevented S100A4-induced plasmin formation in the endothelial cell culture. Local plasmin formation induced by circulating S100A4 could contribute to tumor-induced angiogenesis and metastasis formation that makes this protein an attractive target for new anti-cancer and anti-angiogenic therapies.