Bone tissue engineering techniques are a promising alternative for the use of autologous bone grafts to reconstruct bone defects in the oral and maxillofacial region. However, for successful bone regeneration, adequate vascularization is a prerequisite. This review presents and discusses the application of stem cells and new strategies to improve vascularization, which may lead to feasible clinical applications. Multiple sources of stem cells have been investigated for bone tissue engineering. The stromal vascular fraction (SVF) of human adipose tissue is considered a promising single source for a heterogeneous population of essential cells with, amongst others, osteogenic and angiogenic potential. Enhanced vascularization of tissue-engineered grafts can be achieved by different mechanisms: vascular ingrowth directed from the surrounding host tissue to the implanted graft, vice versa, or concomitantly. Vascular ingrowth into the implanted graft can be enhanced by (i) optimizing the material properties of scaffolds and (ii) their bioactivation by incorporation of growth factors or cell seeding. Vascular ingrowth directed from the implanted graft towards the host tissue can be achieved by incorporating the graft with either (i) preformed microvascular networks or (ii) microvascular fragments (MF). The latter may have stimulating actions on both vascular ingrowth and outgrowth, since they contain angiogenic stem cells like SVF, as well as vascularized matrix fragments. Both adipose tissue-derived SVF and MF are cell sources with clinical feasibility due to their large quantities that can be harvested and applied in a one-step surgical procedure. During the past years, important advancements of stem cell application and vascularization in bone tissue regeneration have been made. The development of engineered in vitro 3D models mimicking the bone defect environment would facilitate new strategies in bone tissue engineering. Successful clinical application requires innovative future investigations enhancing vascularization.