Peripheral vascular disease is one of the major vascular complications in individuals suffering from diabetes and in the elderly that is associated with significant burden in terms of morbidity and mortality. Stem cell therapy is being tested as an attractive alternative to traditional surgery to prevent and treat this disorder. The goal of this study was to enhance the protective and reparative potential of marrow-isolated adult multilineage inducible (MIAMI) cells by incorporating them within a bio-inspired construct (BIC) made of two layers of gelatin B electrospun nanofibers. We hypothesized that the BIC would enhance MIAMI cell survival and engraftment, ultimately leading to a better functional recovery of the injured limb in our mouse model of critical limb ischemia compared to MIAMI cells used alone. Our study demonstrated that MIAMI cell-seeded BIC resulted in a wide range of positive outcomes with an almost full recovery of blood flow in the injured limb, thereby limiting the extent of ischemia and necrosis. Functional recovery was also the greatest when MIAMI cells were combined with BICs, compared to MIAMI cells alone or BICs in the absence of cells. Histology was performed 28 days after grafting the animals to explore the mechanisms at the source of these positive outcomes. We observed that our critical limb ischemia model induces an extensive loss of muscular fibers that are replaced by intermuscular adipose tissue (IMAT), together with a highly disorganized vascular structure. The use of MIAMI cells-seeded BIC prevented IMAT infiltration with some clear evidence of muscular fibers regeneration.