It is thought that degradation of nuclear proteins by the ubiquitylation system requires nuclear-cytoplasmic trafficking of E3 ubiquitin ligases. The von Hippel-Lindau (VHL) tumor suppressor protein is the substrate recognition component of a Cullin-2-containing E3 ubiquitin ligase that recruits hypoxia-inducible factor (HIF) for oxygen-dependent degradation. We demonstrated that VHL engages in nuclear-cytoplasmic trafficking that requires ongoing transcription to promote efficient HIF degradation. Here, we report the identification of a discreet motif, DXGX(2)DX(2)L, that directs transcription-dependent nuclear export of VHL and which is targeted by naturally occurring mutations associated with renal carcinoma and polycythemia in humans. The DXGX(2)DX(2)L motif is also found in other proteins, including poly(A)-binding protein 1, to direct its transcription-dependent nuclear export. We define DXGX(2)DX(2)L as TD-NEM (transcription-dependent nuclear export motif), since inhibition of transcription by actinomycin D or 5,6-dichlorobenzimidazole abrogates its nuclear export activity. Disease-causing mutations of key residues of TD-NEM restrain the ability of VHL to efficiently mediate oxygen-dependent degradation of HIF by altering its nuclear export dynamics without affecting interaction with its substrate. These results identify a novel nuclear export motif, further highlight the role of nuclear-cytoplasmic shuttling of E3 ligases in degradation of nuclear substrates, and provide evidence that disease-causing mutations can target subcellular trafficking.