Mesenchymal stem cells (MSC) are multipotent postnatal stem cells, involved in the treatment of ischemic vascular diseases. We investigate the ability of MSC, exposed to short-term hypoxic conditions, to participate in vascular and tissue regeneration in an in vivo model of hindlimb ischemia. Transplantation of hypoxic preconditioned murine MSC (HypMSC) enhanced skeletal muscle regeneration at day 7, improved blood flow and vascular formation compared to injected nonpreconditioned MSC (NormMSC). These observed effects were correlated with an increase in HypMSC engraftment and a putative role in necrotic skeletal muscle fiber clearance. Moreover, HypMSC transplantation resulted in a large increase in Wnt4 (wingless-related MMTV integration site 4) expression and we demonstrate its functional significance on MSC proliferation and migration, endothelial cell (EC) migration, as well as myoblast differentiation. Furthermore, suppression of Wnt4 expression in HypMSC, abrogated the hypoxia-induced vascular regenerative properties of these cells in the mouse hindlimb ischemia model. Our data suggest that hypoxic preconditioning plays a critical role in the functional capabilities of MSC, shifting MSC location in situ to enhance ischemic tissue recovery, facilitating vascular cell mobilization, and skeletal muscle fiber regeneration via a paracrine Wnt-dependent mechanism.