Emerging evidence has implicated the role of tumor initiating cells (TICs) in the process of cancer metastasis. The mechanism underlying the conversion of TICs from stationary to invasive remains to be characterized. In this report, we employed less invasive breast cancer TICs, SK-3rd, that displays CD44(high)/CD24(low) with high mammosphere-forming and tumorigenic capacities, to investigate the mechanism by which stationary TICs are converted to invasive TICs. Invasive ability of SK-3rd TICs was markedly enhanced when the cells were cultured under hypoxic conditions. Given the role of membrane type 1-matrix metalloproteinase (MT1-MMP) in cancer invasion/metastasis, we explored a possible involvement of MT1-MMP in hypoxia-induced TIC invasion. Silencing of MT1-MMP by a shRNA approach resulted in diminution of hypoxia-induced cell invasion in vitro and metastasis in vivo. Under hypoxic conditions, MT1-MMP redistributed from cytoplasmic storage pools to the cell surface of TICs, which coincides with the increased cell invasion. In addition, CD44, a cancer stem-like cell marker, inversely correlated with increased cell surface MT1-MMP. Interestingly, cell surface MT1-MMP gradually disappeared when the hypoxia-treated cells were switched to normoxia, suggesting the plasticity of TICs in response to oxygen content. Furthermore, we dissected the pathways leading to upregulated MT1-MMP in cytoplasmic storage pools under normoxic conditions, by demonstrating a cascade involving Twist1-miR10b-HoxD10 leading to enhanced MT1-MMP expression in SK-3rd TICs. These observations suggest that MT1-MMP is a key molecule capable of executing conversion of stationary TICs to invasive TICs under hypoxic conditions and thereby controlling metastasis.