The TRE17 (USP6/TRE-2) oncogene induces tumorigenesis in both humans and mice. However, little is known regarding its regulation or mechanism of transformation. TRE17 encodes a TBC (Tre-2/Bub2/Cdc16)/Rab GTPase-activating protein homology domain at its N terminus and a ubiquitin-specific protease at its C terminus. In the current study, we identified the ubiquitous calcium (Ca2+)-binding protein calmodulin (CaM) as a novel binding partner for TRE17. CaM bound directly to TRE17 in a Ca2+-dependent manner both in vitro and in vivo. The CaM-binding site was mapped to two hydrophobic motifs near the C terminus of the TBC domain. Point mutations within these motifs significantly reduced the interaction of TRE17 with CaM. We further found that TRE17 is monoubiquitinated and promotes its own deubiquitination in vivo. CaM binding-deficient mutants of TRE17 exhibited significantly reduced monoubiquitination, suggesting that binding of Ca2+/CaM to TRE17 promotes this modification. Consistent with this notion, treatment of cells with the CaM inhibitor W7 reduced levels of TRE17 monoubiquitination. Interestingly, the calcium ionophore A23187 induced accumulation of a polyubiquitinated TRE17 species. The effect of A23187 was attenuated in CaM binding-deficient mutants of TRE17. Taken together, these studies indicate a role for Ca2+/CaM in regulating ubiquitination through direct interaction with TRE17.