Here we investigated whether endothelial colony forming cells (ECFC) and mesenchymal progenitor cells (MPC) form vascular networks and restore blood flow in ischemic skeletal muscle, and whether host myeloid cells play a role. ECFC + MPC, ECFC alone, MPC alone, or vehicle alone were injected into the hind limb ischemic muscle one day after ligation of femoral artery and vein. At day 5, hind limbs injected with ECFC + MPC showed greater blood flow recovery compared with ECFC, MPC, or vehicle. Tail vein injection of human endothelial specific Ulex europaeus agglutinin-I demonstrated an increased number of perfused human vessels in ECFC + MPC compared with ECFC. In vivo bioluminescence imaging showed ECFC persisted for 14 days in ECFC + MPC-injected hind limbs. Flow cytometric analysis of ischemic muscles at day 2 revealed increased myeloid lineage cells in ECFC + MPC-injected muscles compared to vehicle-injected muscles. Neutrophils declined by day 7, while the number of myeloid cells, macrophages, and monocytes did not. Systemic myeloid cell depletion with anti-Gr-1 antibody blocked the improved blood flow observed with ECFC + MPC and reduced ECFC and MPC retention. Our data suggest that ECFC + MPC delivery could be used to reestablish blood flow in ischemic tissues, and this may be enhanced by coordinated recruitment of host myeloid cells.