The Drosophila HIFalpha homologue, Sima, is localized mainly in the cytoplasm in normoxia and accumulates in the nucleus upon hypoxic exposure. We have characterized the mechanism governing Sima oxygen-dependent subcellular localization and found that Sima shuttles continuously between the nucleus and the cytoplasm. We have previously shown that nuclear import depends on an atypical bipartite nuclear localization signal mapping next to the C-terminus of the protein. We show here that nuclear export is mediated in part by a CRM1-dependent nuclear export signal localized in the oxygen-dependent degradation domain (ODDD). CRM1-dependent nuclear export requires both oxygen-dependent hydroxylation of a specific prolyl residue (Pro850) in the ODDD, and the activity of the von Hippel Lindau tumor suppressor factor. At high oxygen tension rapid nuclear export of Sima occurs, whereas in hypoxia, Sima nuclear export is largely inhibited. HIFalpha/Sima nucleo-cytoplasmic localization is the result of a dynamic equilibrium between nuclear import and nuclear export, and nuclear export is modulated by oxygen tension.