GTP cyclohydrolase 1 (GTPCH1) is the rate-limiting enzyme in the de novo synthesis of tetrahydrobiopterin (BH4). GTPCH1 protein degradation has been reported in animal models of several diseases, including diabetes mellitus and hypertension. However, the molecular mechanisms by which GTPCH1 is degraded remain uncharacterized. Here we report a novel non-covalent interaction between polyubiquitin and GTPCH1 in vitro and in vivo. The non-covalent binding of GTPCH1 to polyubiquitin via an ubiquitin-binding domain (UBD) results in ubiquitination and degradation. Ectopic expression of ubiquitin in cultured cells accelerated GTPCH1 degradation. In cultured cells and in vitro assays, Lys48-linked ubiquitin chains, but not Lys63-linked chains, interacted with GTPCH1 and targeted it for degradation. Consistently, proteasome inhibition attenuated GTPCH1 degradation. Finally, direct mutagenesis of an isoleucine (Ile131) in the hydrophobic patch of the GTPCH1 UBD affected its ubiquitin binding and the enzyme stability. Taken together, we conclude that GTPCH1 non-covalently interacts with polyubiquitin via an ubiquitin-binding domain. The polyubiquitin binding directs GTPCH1 ubiquitination and proteasome degradation.