Metastasis is the primary cause of mortality from cancer, but the mechanisms leading to metastasis are poorly understood. In particular, relatively little is known about metastasis in cancers of mesenchymal origins, which are known as sarcomas. Approximately ten proteins have been characterized as 'metastasis suppressors', but how these proteins function and are regulated is, in general, not well understood. Gp78 (also known as AMFR or RNF45) is a RING finger E3 ubiquitin ligase that is integral to the endoplasmic reticulum (ER) and involved in ER-associated degradation (ERAD) of diverse substrates. Here we report that expression of gp78 has a causal role in the metastasis of an aggressive human sarcoma and that this prometastatic activity requires the E3 activity of gp78. Further, gp78 associates with and targets the transmembrane metastasis suppressor, KAI1 (also known as CD82), for degradation. Suppression of gp78 increases KAI1 abundance and reduces the metastatic potential of tumor cells, an effect that is largely blocked by concomitant suppression of KAI1. An inverse relationship between these proteins was confirmed in a human sarcoma tissue microarray. Whereas most previous efforts have focused on genetic mechanisms for the loss of metastasis suppressor genes, our results provide new evidence for post-translational downregulation of a metastasis suppressor by its ubiquitin ligase, resulting in abrogation of its metastasis-suppressing effects.