The RING finger E3 ubiquitin ligase Siah2 is implicated in control of diverse cellular biological events, including MAPK signaling and hypoxia. Here we demonstrate that Siah2 is subject to regulation by the deubiquitinating enzyme USP13. Overexpression of USP13 increases Siah2 stability by attenuating its autodegradation. Consequently, the ability of Siah2 to target its substrates prolyl hydroxylase 3 and Spry2 (Sprouty2) for ubiquitin-mediated proteasomal degradation is attenuated. Conversely, inhibition of USP13 expression with corresponding shRNA decreases the stability of both Siah2 and its substrate Spry2. Thus, USP13 limits Siah2 autodegradation and its ubiquitin ligase activity against its target substrates. Strikingly, the effect of USP13 on Siah2 is not mediated by its isopeptidase activity: mutations in its ubiquitin-binding sequences positioned within the ubiquitin-specific processing protease and ubiquitin-binding domains, but not within putative catalytic sites, abolish USP13 binding to and effect on Siah2 autodegradation and targeted ubiquitination. Notably, USP13 expression is attenuated in melanoma cells maintained under hypoxia, thereby relieving Siah2 inhibition and increasing its activity under low oxygen levels. Significantly, on melanoma tissue microarray, high nuclear expression of USP13 coincided with high nuclear expression of Siah2. Overall, this study identifies a new layer of Siah2 regulation mediated by USP13 binding to ubiquitinated Siah2 protein with a concomitant inhibitory effect on its activity under normoxia.