Cancer metastasis is a disease of extreme clinical relevance, as it is responsible for more than 90% of cancer-associated mortality. The molecular mechanism and critical regulators involved in this complex multi-stage process of metastasis is poorly deciphered in soft tissue sarcomas (STS), a heterogeneous group of rare tumors with high metastatic potential. Therefore, we aimed at identifying miRNA and transcription factor (TF) regulatory networks and paths in STS metastasis. We integrated mRNA and miRNA expression profiles with curated regulations (TF→gene, TF→miRNA, miRNA→gene) from different databases and constructed a potentially active regulatory sub-network in STS metastasis. From functional and topological analysis, we found nine novel regulators of Notch signaling sub-network which are conjectured to play critical role in metastasis of STS. This illustrated that the sub-network is promising for identification of critical regulators. Further analysis deploying our developed tool 'RiNAcyc' and computing coverage ratio of known STS associated genes and miRNAs identified a 15 node active path. This potential path highlights the crucial role of BMP2, hsa-miR-24, AP2 and MYC as the up-stream regulators of the path and hsa-miR-215 and TYMS as potential indicator of chemotherapeutic benefit in STS metastasis.