HIF-1α is a master regulator of oxygen homeostasis involved in different stages of cancer development. Thus, HIF-1α inhibition represents an interesting target for anti-cancer therapy. It was recently shown that the HIF-1α interaction with NQO1 inhibits proteasomal degradation of the former, thus suggesting that targeting the stability and/or function of NQO1 could lead to the destabilization of HIF-1α as a therapeutic approach. Since the molecular interactions of NQO1 with HIF-1α are beginning to be unraveled, in this review we discuss: (1) Structure–function relationships of HIF-1α; (2) our current knowledge on the intracellular functions and stability of NQO1; (3) the pharmacological modulation of NQO1 by small ligands regarding function and stability; (4) the potential effects of genetic variability of NQO1 in HIF-1α levels and function; (5) the molecular determinants of NQO1 as a chaperone of many different proteins including cancer-associated factors such as HIF-1α, p53 and p73α. This knowledge is then further discussed in the context of potentially targeting the intracellular stability of HIF-1α by acting on its chaperone, NQO1. This could result in novel anti-cancer therapies, always considering that the substantial genetic variability in NQO1 would likely result in different phenotypic responses among individuals.