The tumour stroma is an active participant during cancer progression. Stromal cells promote tumour progression and metastasis through multiple mechanisms including enhancing tumour invasiveness and angiogenesis, and suppressing immune surveillance. We report here that miR-126/miR-126^*, a microRNA pair derived from a single precursor, independently suppress the sequential recruitment of mesenchymal stem cells and inflammatory monocytes into the tumour stroma to inhibit lung metastasis by breast tumour cells in a mouse xenograft model. miR-126/miR-126^* directly inhibit stromal cell-derived factor-1 alpha (SDF-1α) expression, and indirectly suppress the expression of chemokine (C–C motif) ligand 2 (Ccl2) by cancer cells in an SDF-1α-dependent manner. miR-126/miR-126^* expression is downregulated in cancer cells by promoter methylation of their host gene Egfl7. These findings determine how this microRNA pair alters the composition of the primary tumour microenvironment to favour breast cancer metastasis, and demonstrate a correlation between miR-126/126^* downregulation and poor metastasis-free survival of breast cancer patients.