In this study, we established and characterized human umbilical cord blood-derived mesenchymal stem cells (hUCB-MSCs) from four different donors. However, the hUCB-MSCs showed remarkable variations in their therapeutic efficacy for repairing rat infarcted myocardium (including the process of angiogenesis) 8 weeks after transplantation. In addition, we observed that the level of vascular endothelial growth factor (VEGF) is correlated with the therapeutic efficacy of the four hUCB-MSCs. Next, to investigate the practical application of hUCB-MSCs, we searched for surface signature molecules that could serve as indicators of therapeutic efficacy. The gene for N-cadherin was the only cell surface gene that was highly expressed in the most effective hUCB-MSCs, both at the transcriptional and translational levels. We observed downregulation and upregulation of VEGF in response to N-cadherin blocking and N-cadherin overexpression, respectively. Activation of extracellular signal-regulated kinase (ERK), but not protein kinase B, was increased when N-cadherin expression was increased, whereas disruption of N-cadherin-mediated cell-cell contact induced suppression of ERK activation and led to VEGF downregulation. Moreover, by investigating hUCB-MSCs overexpressing N-cadherin or N-cadherin knockdown hUCB-MSCs, we confirmed the in vivo function of N-cadherin. In addition, we observed that DiI-labeled hUCB-MSCs express N-cadherin in the peri-infarct area and interact with cardiomyocytes.