Carcinogenesis consists of oncogenesis and metastasis, and intriguingly microRNAs (miRNAs) are involved in both processes. Although aberrant miRNA activities are prevalent in diverse tumor types, the exact mechanisms for how they regulate cancerous processes are not always clear. To this end, we performed a large-scale pan-cancer analysis via a novel probabilistic approach to infer recurrent miRNA-target interactions implicated in 12 cancer types using data from The Cancer Genome Atlas. We discovered ~20,000 recurrent miRNA regulations, which are enriched for cancer-related miRNAs/genes. Notably, miRNA 200 family (miR-200/141/429) is among the most prominent miRNA regulators, which is known to be involved in metastasis. Importantly, the recurrent miRNA regulatory network is not only enriched for cancer pathways but also for extracellular matrix (ECM) organization and ECM-receptor interactions. The results suggest an intriguing cancer mechanism involving miRNA-mediated cell-to-cell communication, which possibly involves delivery of tumorigenic miRNA messengers to adjacent cells via exosomes. Finally, survival analysis revealed 414 recurrent-prognostic associations, where both gene and miRNA involved in each interaction conferred significant prognostic power in one or more cancer types. Together, our comprehensive pan-cancer analysis provided not only biological insights into metastasis but also brought to bear the clinical relevance of the proposed recurrent miRNA-gene associations.