Eukaryotic cells require iron for survival and have developed regulatory mechanisms for maintaining appropriate intracellular iron concentrations. The degradation of iron regulatory protein 2 (IRP2) in iron-replete cells is a key event in this pathway, but the E3 ubiquitin ligase responsible for its proteolysis has remained elusive. We found that a SKP1-CUL1-FBXL5 ubiquitin ligase protein complex associates with and promotes the iron-dependent ubiquitination and degradation of IRP2. The F-box substrate adaptor protein FBXL5 was degraded upon iron and oxygen depletion in a process that required an iron-binding hemerythrin-like domain in its N terminus. Thus, iron homeostasis is regulated by a proteolytic pathway that couples IRP2 degradation to intracellular iron levels through the stability and activity of FBXL5.