Hypoxia is a key factor responsible for the failure of therapeutic response in most solid tumors and promotes the acquisition of tumor resistance to various antitumor immune effectors. Reshaping the hypoxic immune suppressive tumor microenvironment to improve cancer immunotherapy is still a relevant challenge. We investigated the impact of inhibiting HIF-1α transcriptional activity on cytotoxic immune cell infiltration into B16-F10 melanoma. We showed that tumors expressing a deleted form of HIF-1α displayed increased levels of NK and CD8+ effector T cells in the tumor microenvironment, which was associated with high levels of CCL2 and CCL5 chemokines. We showed that combining acriflavine, reported as a pharmacological agent preventing HIF-1α/HIF-1β dimerization, dramatically improved the benefit of cancer immunotherapy based on TRP-2 peptide vaccination and anti-PD-1 blocking antibody. In melanoma patients, we revealed that tumors exhibiting high CCL5 are less hypoxic, and displayed high NK, CD3+, CD4+ and CD8+ T cell markers than those having low CCL5. In addition, melanoma patients with high CCL5 in their tumors survive better than those having low CCL5. This study provides the pre-clinical proof of concept for a novel triple combination strategy including blocking HIF-1α transcription activity along vaccination and PD-1 blocking immunotherapy.