Abnormal rates of growth together with metastatic potential and lack of susceptibility to cellular signals leading to apoptosis are widely investigated characteristics of tumors that develop via genetic or epigenetic mechanisms. Moreover, in the growing tumor, cells are exposed to insufficient nutrient supply, low oxygen availability (hypoxia) and/or reactive oxygen species. These physiological stresses force them to switch into more adaptable and aggressive phenotypes. This paper summarizes the role of two key mediators of cellular stress responses, namely p53 and HIF, which significantly affect cancer progression and compromise treatment outcomes. Furthermore, it describes cross-talk between these factors.