Cytolytic activity by CD8⁺ cytotoxic T lymphocytes (CTLs) is a powerful strategy for the elimination of intracellular pathogens and tumor cells. The destructive capacity of CTLs is progressively dampened during chronic infection, yet the environmental cues and molecular pathways that influence immunological 'exhaustion' remain unclear. Here we found that CTL immunity was regulated by the central transcriptional response to hypoxia, which is controlled in part by hypoxia-inducible factors (HIFs) and the von Hippel–Lindau tumor suppressor VHL. Loss of VHL, the main negative regulator of HIFs, led to lethal CTL-mediated immunopathology during chronic infection, and VHL-deficient CTLs displayed enhanced control of persistent viral infection and neoplastic growth. We found that HIFs and oxygen influenced the expression of pivotal transcription, effector and costimulatory-inhibitory molecules of CTLs, which was relevant to strategies that promote the clearance of viruses and tumors.