Inactivation of von Hippel-Lindau tumor-suppressor protein (pVHL) is associated with von Hippel-Lindau disease, an inherited cancer syndrome, as well as the majority of patients with sporadic clear cell renal cell carcinoma (RCC). Although the involvement of pVHL in oxygen sensing through targeting hypoxia-inducible factor-α subunits to ubiquitin-dependent proteolysis has been well documented, less is known about pVHL regulation under both normoxic and hypoxic conditions. We found that pVHL levels decreased in hypoxia and that hypoxia-induced cell cycle arrest is associated with pVHL expression in RCC cells. pVHL levels fluctuate during the cell cycle, paralleling cyclin B1 levels, with decreased levels in mitosis and G1. pVHL contains consensus destruction (D) box sequences, and pVHL associates with Cdh1, an activator of the anaphase-promoting complex/cyclosome (APC/C) E3 ubiquitin ligase. We show that pVHL has a decreased half-life in G1, Cdh1 downregulation results in increased pVHL expression, whereas Cdh1 overexpression results in decreased pVHL expression. Taken together, these results suggest that pVHL is a novel substrate of APC/C(Cdh1). D box-independent pVHL degradation was also detected, indicating that other ubiquitin ligases are also activated for pVHL degradation.