Recent studies have demonstrated that cancer stem cells play an important role in the pathobiology of head and neck squamous cell carcinomas (HNSCC). However, little is known about functional interactions between head and neck cancer stem-like cells (CSC) and surrounding stromal cells. Here, we used aldehyde dehydrogenase activity and CD44 expression to sort putative stem cells from primary human HNSCC. Implantation of 1,000 CSC (ALDH+CD44+Lin-) led to tumors in 13 (out of 15) mice, whereas 10,000 noncancer stem cells (ALDH-CD44-Lin-) resulted in 2 tumors in 15 mice. These data demonstrated that ALDH and CD44 select a subpopulation of cells that are highly tumorigenic. The ability to self-renew was confirmed by the observation that ALDH+CD44+Lin- cells sorted from human HNSCC formed more spheroids (orospheres) in 3-D agarose matrices or ultra-low attachment plates than controls and were serially passaged in vivo. We observed that approximately 80% of the CSC were located in close proximity (within 100-μm radius) of blood vessels in human tumors, suggesting the existence of perivascular niches in HNSCC. In vitro studies demonstrated that endothelial cell-secreted factors promoted self-renewal of CSC, as demonstrated by the upregulation of Bmi-1 expression and the increase in the number of orospheres as compared with controls. Notably, selective ablation of tumor-associated endothelial cells stably transduced with a caspase-based artificial death switch (iCaspase-9) caused a marked reduction in the fraction of CSC in xenograft tumors. Collectively, these findings indicate that endothelial cell-initiated signaling can enhance the survival and self-renewal of head and neck CSC.