Patients with the mesenchymal subtype colorectal cancer (CRC) have a poor prognosis, in particular patients with stroma-rich tumors and aberrant SMAD4 expression. We hypothesized that interactions between SMAD4-deficient CRC cells and cancer-associated fibroblasts provide a biological explanation. In transwell invasion assays, fibroblasts increased the invasive capacity of SMAD4-deficient HT29 CRC cells, but not isogenic SMAD4-proficient HT29 cells. A TGF-β/BMP-specific array showed BMP2 upregulation by fibroblasts upon stimulation with conditioned medium from SMAD4-deficient CRC cells, while also stimulating their invasion. In a mouse model for experimental liver metastasis, the co-injection of fibroblasts increased metastasis formation of SMAD4-deficient CRC cells (p = 0.02) but not that of SMAD4-proficient CRC cells. Significantly less metastases were seen in mice co-injected with BMP2 knocked-down fibroblasts. Fibroblast BMP2 expression seemed to be regulated by TRAIL, a factor overexpressed in SMAD4-deficient CRC cells. In a cohort of 146 stage III CRC patients, we showed that patients with a combination of high stromal BMP2 expression and the loss of tumor SMAD4 expression had a significantly poorer overall survival (HR 2.88, p = 0.04). Our results suggest the existence of a reciprocal loop in which TRAIL from SMAD4-deficient CRC cells induces BMP2 in fibroblasts, which enhances CRC invasiveness and metastasis.