It has become clear that tumor stroma components are engaged in an active and complex molecular cross-talk that has serious implications for immunological recognition of tumor cells in shaping the microenvironment. Hypoxia which is a major component of tumor microenvironment influences the characteristics of neoplasia by favoring heterogeneity, invasiveness, metastatic potency and tumor progression. In this regard, an important mode of communication between carcinoma cells and immune cells may involve tumor-derived microvesicles, which are able to carry lipids, proteins, mRNAs and miRNAs. This review covers new evidence indicating that the efficacy of the cell-mediated cytotoxicity (CTLs and NK) may be dependent on hypoxia induced miRNA and microvesicles in the tumor microenvironment by inhibiting the efficacy of natural host anti-tumor immune response and improving the ability of tumors to avoid immunosurveillance. This emphasizes that hypoxic tumors actively develop additional mechanisms to suppress the sensing of the immunologic danger signals in order to survive and propagate without inciting anti-tumor immunity.