To gain insight into miRNA regulation in metastasis formation, we used a metastasis cell line model that allows investigation of extravasation and colonization of circulating cancer cells to lungs in mice. Using global miRNA profiling, 28 miRNAs were found to exhibit significantly altered expression between isogenic metastasizing and non-metastasizing cancer cells, with miR-155 being the most differentially expressed. Highly metastatic mesenchymal-like CL16 cancer cells showed very low miR-155 expression, and miR-155 overexpression in these cells lead to significantly decreased tumor burden in lungs when injected intravenously in immunodeficient mice. Our experiments addressing the underlying mechanism of the altered tumor burden revealed that miR-155-overexpressing CL16 cells were less invasive than CL16 control cells in vitro, while miR-155 overexpression had no effect on cancer cell proliferation or apoptosis in established lung tumors. To identify proteins regulated by miR-155 and thus delineate its function in our cell model, we compared the proteome of xenograft tumors derived from miR-155-overexpressing CL16 cells and CL16 control cells using mass spectrometry-based proteomics. >4,000 proteins were identified, of which 92 were consistently differentially expressed. Network analysis revealed that the altered proteins were associated with cellular functions such as movement, growth and survival as well as cell-to-cell signaling and interaction. Downregulation of the three metastasis-associated proteins ALDH1A1, PIR and PDCD4 in miR-155-overexpressing tumors was validated by immunohistochemistry. Our results demonstrate that miR-155 inhibits the ability of cancer cells to extravasate and/or colonize at distant organs and brings additional insight into the complexity of miR-155 regulation in metastatic seeding.