Mutations in the von Hippel-Lindau (VHL) tumor suppressor gene are responsible for a hereditary cancer syndrome characterized by high susceptibility to hemangioblastomas of the retina and central nervous system, pheochromocytomas, and renal cell carcinomas. In agreement with its role as a tumor suppressor, the vast majority of spontaneous clear cell carcinomas of the kidney present loss of heterozygosity at the VHL locus. Recently, it has been shown that VHL works as the substrate recognition component of an E3 ubiquitination complex that targets the hypoxia-inducible factor (HIF) for proteosomal degradation. Under normal oxygen tension, the half-life of HIF transcription factors is extremely short because of its high degradation rate by the proteasome, resulting in undetectable HIF activity in normal cells. However, in VHL-deficient tumor cells, the HIF transcriptional pathway is constitutively activated because of impaired ubiquitination of this transcription factor. To target VHL-deficient tumors, we have exploited this feature to develop a conditionally replicative adenovirus (Ad9xHRE1A), the replication of which is HIF dependent. In this new oncolytic adenovirus, the expression of the E1A gene is controlled by an optimized minimal promoter containing HIF recognition elements. Here, we show that the induction of the E1A gene, as well as the viral replication and cytolytic effect of Ad9xHRE1A, are dependent on HIF activity. As a consequence, this virus efficiently kills VHL-deficient cells both in vitro and in vivo, as well as cells growing under hypoxic conditions. These data suggest that Ad9xHRE1A could be used as a highly specific therapy for VHL-deficient cancers and probably many other tumors that show extensive hypoxic areas or increased HIF activity by genetic alterations other than VHL loss.