The iron-sensing protein FBXL5 is the substrate adaptor for a SKP1-CUL1-RBX1 E3 ubiquitin ligase complex that regulates the degradation of iron regulatory proteins (IRPs). Here, we describe a mechanism of FBXL5 regulation involving its interaction with the cytosolic Fe-S cluster assembly (CIA) targeting complex composed of MMS19, FAM96B, and CIAO1. We demonstrate that the CIA-targeting complex promotes the ability of FBXL5 to degrade IRPs. In addition, the FBXL5-CIA-targeting complex interaction is regulated by oxygen (O2) tension displaying a robust association in 21% O2 that is severely diminished in 1% O2 and contributes to O2-dependent regulation of IRP degradation. Together, these data identify a novel oxygen-dependent signaling axis that links IRP-dependent iron homeostasis with the Fe-S cluster assembly machinery.