Hypoxia or oxygen deficiency is a salient feature of solid tumors. Hypoxic tumors are often resistant to conventional cancer therapies, and tumor hypoxia correlates with advanced stages of malignancy. Hypoxic tumors appear to be poorly differentiated. Increasing evidence suggests that hypoxia has the potential to inhibit tumor cell differentiation and thus plays a direct role in the maintenance of cancer stem cells. Studies have also shown that hypoxia blocks differentiation of mesenchymal stem/progenitor cells, a potential source of tumor-associated stromal cells. It is therefore likely that hypoxia may have a profound impact on the evolution of the tumor stromal microenvironment. These observations have led to the emergence of a novel paradigm for a role of hypoxia in facilitating tumor progression. Hypoxia may help create a microenvironment enriched in poorly differentiated tumor cells and undifferentiated stromal cells. Such an undifferentiated hypoxic microenvironment may provide essential cellular interactions and environmental signals for the preferential maintenance of cancer stem cells. This hypothesis suggests that effectively targeting hypoxic cancer stem cells is a key to successful tumor control.