The transformation of a normal cell to cancer requires the derail of multiple pathways. Normal signaling in a cell is regulated at multiple stages by the presence of feedback loops, calibration of levels of proteins by their regulated turnover, and posttranscriptional regulation, to name a few. The tumor suppressor protein FBXO31 is a component of the SCF E3 ubiquitin ligase and is required to arrest cells at G1 following genotoxic stresses. Due to its growth-suppression activity, it is underexpressed in many cancers. However, the molecular mechanism underlying the translational regulation of FBXO31 remains unclear. Here we show that the oncogenic microRNAs miR-93 and miR-106a repress FBXO31, resulting in the upregulation of Slug, which is involved in epithelial-mesenchymal transition and cell invasion. FBXO31 targets and ubiquitylates Slug for proteasomal degradation. However, this mechanism is repressed in breast tumors where miR-93 and miR-106a are overexpressed. Our study further unravels an interesting mechanism whereby Slug drives the expression of miR-93 and miR-106a, thus establishing a positive feedback loop to maintain an invasive phenotype. Together, these results establish the presence of interplay between microRNAs and the ubiquitination machinery, which together regulate cancer cell invasion.