Hypoxia is a prominent feature of malignant tumors that are characterized by angiogenesis and vascular hyperpermeability. Vascular permeability factor/vascular endothelial growth factor (VPF/VEGF) has been shown to be up-regulated in the vicinity of necrotic tumor areas, and hypoxia potently induces VPF/VEGF expression in several tumor cell lines in vitro. Here we report that hypoxia-induced VPF/VEGF expression is mediated by increased transcription and mRNA stability in human M21 melanoma cells. RNA-binding/electrophoretic mobility shift assays identified a single 125-bp AU-rich element in the 3' untranslated region that formed hypoxia-inducible RNA-protein complexes. Hypoxia-induced expression of chimeric luciferase reporter constructs containing this 125-bp AU-rich hypoxia stability region were significantly higher than constructs containing an adjacent 3' untranslated region element without RNA-binding activity. Using UV-cross-linking studies, we have identified a series of hypoxia-induced proteins of 90/88 kDa, 72 kDa, 60 kDa, 56 kDa, and 46 kDa that bound to the hypoxia stability region element. The 90/88-kDa and 60-kDa species were specifically competed by excess hypoxia stability region RNA. Thus, increased VPF/VEGF mRNA stability induced by hypoxia is mediated, at least in part, by specific interactions between a defined mRNA stability sequence in the 3' untranslated region and distinct mRNA-binding proteins in human tumor cells.