Peripheral vascular disease (PVD) is a growing medical problem in Western societies and presents itself mainly in two different clinical forms. Intermittent claudication is an early moderate manifestation, while patients with critical limb ischemia suffer from severe muscle tissue loss or ulcers and are at high risk for limb amputation. Unfortunately, many patients cannot be helped with currently available surgical or endovascular revascularization procedures because of the complex anatomy of the vascular occlusion and/or the presence of other risk factors. Noninvasive stem cell therapy has been proposed as an alternative for such patients. Although pioneering clinical experience with stem cell-related therapy seems promising, it is too early for general clinical use of this technique, since many questions remain unanswered. Indeed, while questions about safety, dose, and administration route/timing/frequency are the first ones to be addressed when designing a stem cell-based clinical approach, there is accumulating evidence from recent (pre-)clinical studies that other issues may also be at stake. For instance, the choice of stem cells to be used and its precise mechanism of action, the need/possibility for concurrent tissue regeneration in case of irreversible tissue loss, the differentiation degree and specific vascular identity of the transplanted cells, and the long-term survival of engrafted cells in the absence of a normal supportive tissue environment should be well considered. Here, rather than presenting a comprehensive and extensive overview on the current literature on stem/progenitor cells and revascularization, we highlight some of the outstanding issues emerging from the recent (pre-)clinical literature that may codetermine the successful application of stem cells in a wide range of PVD patients in the future.